[Powered by Google Translate] [Trier Insertion] [Tommy MacWilliam] [Université de Harvard] [C'est CS50.TV] Jetons un coup d'oeil à tri par insertion, un algorithme de prendre une liste de numéros et de les trier. Un algorithme, rappelez-vous, c'est tout simplement une procédure étape par étape pour accomplir une tâche. L'idée de base derrière le tri par insertion, est de diviser notre liste en deux parties, une partie triés et une partie non triés. 

À chaque étape de l'algorithme, un nombre est déplacée de la partie non triés à la partie triée jusqu'à ce que finalement toute la liste est triée. Voici la liste des six numéros non triés - 23, 42, 4, 16, 8, et 15. Étant donné que ces chiffres ne sont pas tout dans l'ordre croissant, ils sont triés. Puisque nous n'avons pas encore commencé le tri, nous allons examiner l'ensemble des six éléments de notre partie non triés. 

Une fois que nous commencer à trier, nous allons mettre ces chiffres triés à la gauche de ceux-ci. Donc, nous allons commencer par 23, le premier élément de la liste. Nous n'avons pas tous les éléments dans notre partie encore triées, nous allons donc considérer simplement 23 soit le début et la fin de notre part triés. Maintenant, notre part triés contient un numéro, 23, et notre portion non triés possède ces cinq numéros. Nous allons maintenant insérer le numéro suivant dans notre partie non triés, 42, dans la partie triée. 

Pour ce faire, nous aurons besoin de comparer la 42 à la 23 - le seul élément de notre part triés jusqu'ici. Quarante-deux est plus grand que 23, donc nous pouvons simplement ajouter 42 à la fin de la partie de la liste triée. Super! Maintenant, notre partie a deux éléments triés et non triés notre partie comporte quatre éléments. Donc, nous allons maintenant passer à la 4, l'élément suivant dans la partie non triés. Alors, où doit-il être placé dans la partie triée? 

Rappelez-vous, nous voulons placer ce chiffre dans l'ordre de tri de sorte que notre partie triée reste correctement triés en tout temps. Si nous plaçons la 4 à la droite de la 42, alors notre liste sera hors d'usage. Donc, nous allons continuer à aller de droite à gauche dans notre partie quelconque. Comme nous nous déplaçons, nous allons passer chaque numéro en bas d'un endroit pour faire de la place pour le nouveau numéro. Okay, 4 est également inférieur à 23, nous ne pouvons pas le placer non plus. Passons le 23 à droite un seul endroit. 

Cela signifie que nous aimerions placer les 4 dans la première fente dans la partie triée. Remarquez comment cet espace dans la liste était déjà vide, parce que nous avons été des éléments mobiles triés de la manière que nous avons rencontrés. Très bien. Donc, nous sommes à mi-chemin. Continuons notre algorithme en insérant le 16 dans la partie triée. Seize ans est inférieur à 42, nous allons donc passer de 42 à droite. Seize ans est également inférieur à 23, nous allons donc passer outre cet élément. 

Maintenant, 16 est supérieur à 4. Donc, il semble que nous aimerions insérer le 16, entre le 4 et le 23. Tout en se déplaçant à travers la partie triée de la liste de droite à gauche, 4 est le premier numéro, nous avons vu que est plus petit que le nombre nous essayons d'insérer. Donc, maintenant nous pouvons insérer le 16 dans ce logement vide, qui, rappelez-vous, nous avons créé par des éléments mobiles dans la partie tri sur comme nous l'avons rencontrés. 

Très bien. Maintenant, nous avons quatre éléments triés et deux éléments non triés. Donc, nous allons déplacer le 8 dans la partie triée. Huit est inférieur à 42. Huit est inférieur à 23. Et la figure 8 est inférieure à 16. Mais 8 est supérieur à 4. Donc, nous aimerions insérer le 8 entre le 4 et le 16. Et maintenant nous avons juste un élément de plus à gauche pour trier - le 15. Quinze est inférieur à 42, Quinze est inférieur à 23. Et 15 est inférieur à 16. 15 mais est supérieure à 8. 

Donc, c'est là que nous voulons faire de notre insertion finale. Et c'est fait. Nous n'avons pas plus d'éléments dans la partie non triés, et notre partie est triée dans l'ordre correct. Les nombres sont ordonnés du plus petit au plus grand. Donc, nous allons jeter un oeil à certains pseudo-code qui décrit les étapes que nous venons effectuées. 

Sur la ligne 1, nous pouvons voir que nous aurons besoin d'itérer sur chaque élément de la liste exception de la première, depuis le premier élément de la partie non triés deviendra tout simplement le premier élément de la partie triée. Sur les lignes 2 et 3, nous gardons une trace de notre place actuelle dans la partie non triés. Élément représente le nombre que nous sommes actuellement en train dans la partie triée, et j représente notre index dans la partie non triés. 

Sur la ligne 4, nous nous parcourons la partie triée de droite à gauche. Nous voulons arrêter l'itération une fois l'élément à gauche de notre position actuelle est inférieure à l'élément que nous essayons d'insérer. Sur la ligne 5, nous déplacer chaque élément que nous rencontrons un espace vers la droite. De cette façon, nous aurons un espace libre d'insérer dans quand nous trouvons le premier élément au moins la partie nous allons. Sur la ligne 6, nous mettons à jour notre comptoir de continuer à déplacer vers la gauche à travers la partie triée. Enfin, sur la ligne 7, nous insérer l'élément dans la partie de la liste triée. 

Nous savons que c'est bon d'insérer dans la position j, parce que nous avons déjà déplacé l'élément qui sert à être là un espace vers la droite. Rappelez-vous, nous allons à travers la partie triée de droite à gauche, mais nous avançons à travers la partie non triés de gauche à droite. Très bien. Jetons maintenant un coup d'oeil à la façon dont l'algorithme de longue durée qui a pris. Nous allons d'abord poser la question combien de temps faut-il pour que cet algorithme afin de fonctionner dans le pire des cas. Rappelez-vous que nous représentons cette durée avec la notation O Big. Afin de régler notre liste, nous avons dû parcourir les éléments dans la partie non triés, et pour chacun de ces éléments, éventuellement au-dessus de tous les éléments dans la partie triée. Intuitivement, cela ressemble à une opération O (n ^ 2). 

En regardant notre pseudo-code, nous avons une boucle imbriquée dans une autre boucle, qui, en effet, ressemble à une opération O (n ^ 2). Toutefois, la partie de la liste triée ne contient pas la liste entière jusqu'à la fin. Pourtant, nous pourrions insérer un nouvel élément au tout début de la partie triée à chaque itération de l'algorithme, ce qui signifie que nous aurions à examiner chaque élément actuellement dans la partie triée. Donc, cela signifie que nous pourrions éventuellement faire une comparaison pour le deuxième élément, deux comparaisons pour le troisième élément, et ainsi de suite. Ainsi, le nombre total d'étapes est la somme des nombres entiers de 1 à la longueur de la liste moins 1. On peut représenter cela avec une sommation. 

Nous n'entrerons pas dans sommations ici, mais il s'avère que cette somme est égale à n (n - 1) sur 2, ce qui est équivalent ^ n 2/2 - n / 2. Quand on parle d'exécution asymptotique, ce n ^ 2 terme va dominer ce terme n. Ainsi, le tri par insertion est Big O (n ^ 2). Que faire si nous avons couru le tri par insertion sur une liste déjà triée. Dans ce cas, nous serions tout simplement mettre en place la partie triés de gauche à droite. Donc, nous allons seulement besoin de l'ordre de n étapes. 

Cela signifie que le tri par insertion a un rendement meilleur des cas de n, que nous représentons avec Ω (n). Et c'est tout pour le tri par insertion, juste un des nombreux algorithmes que nous pouvons utiliser pour trier la liste. Mon nom est Tommy, et c'est CS50. [CS50.TV] Oh, vous ne pouvez pas arrêter cela une fois qu'il démarre. Oh, nous l'avons fait - Boom! >>