[Jouer de la musique] 

DOUG LLOYD: Donc, le tri par insertion est un autre algorithme nous pouvons utiliser pour trier un tableau. L'idée derrière cet algorithme est de construire votre tableau trié en place, déplacer des éléments sur la façon que vous allez, pour faire place. Ce chiffre est légèrement différente de sorte de sélection ou la bulle trier, par exemple, où nous ajustons les emplacements, où nous faisons des swaps. 

Dans ce cas, ce que nous sommes en fait faire est éléments coulissants plus, hors de la voie. Comment fonctionne cet algorithme travailler en pseudo? Eh bien, laissez simplement de dire que l'arbitraire le premier élément de tableau est trié. Nous construisons en place. 

Nous allons aller un élément à la fois et construire, et donc la première chose que nous voyons est un tableau d'un élément. Et par définition, un un élément tableau est trié. 

Ensuite, nous allons répéter ce processus until-- nous répétons le processus suivant jusqu'à ce que tous les éléments sont classés. Regardez le prochain élément non triés et insérer dans la partie triés, en décalant le nombre requis d'éléments sur le chemin. Espérons que cette visualisation vous aidera à voir exactement ce qui est passe avec le tri par insertion. 

Encore une fois, voici notre ensemble du réseau non triés, tous les éléments indiqués en rouge. Et nous allons suivre la étapes de notre pseudo. La première chose que nous faisons, est que nous appelons le premier élément du tableau, triés. Donc, nous sommes juste vas dire cinq ans, vous êtes maintenant triés. 

Ensuite, nous regardons à la prochaine élément non triés du tableau et nous voulons insérer ce dans la partie triés, en déplaçant les éléments sur. Donc deux est la prochaine non triés élément du tableau. Il est clair qu'il appartient avant le cinq, donc ce que nous allons faire est une sorte de tenir deux de côté pour un deuxième, décaler cinq de plus, puis insérez deux avant cinq, où devrait aller. Et maintenant, nous pouvons dire que deux est trié. 

Donc, comme vous pouvez le voir, nous avons seulement jusqu'à présent regardé deux éléments du tableau. Nous avons pas regardé le repos à tous, mais nous avons a obtenu ces deux éléments classés par le moyen de mécanisme de déplacement. 

Donc, nous le répétons à nouveau le processus. Regardez la prochaine non triés élément, qui est un. Tenons cela de côté pour un deuxième, décaler tout fini, et mettre un où il doit aller. 

Encore une fois, encore, nous avons seulement jamais regardé un, deux et cinq. Nous ne savons pas quoi d'autre est à venir, mais nous avons trié ces trois éléments. 

Suivant élément non triés est trois, nous allons donc le mettre de côté. Nous déplaçons sur ce que nous besoin à qui, cette fois, est pas tout comme dans le précédent deux cas, il est juste cinq. Et puis, nous nous en tiendrons à trois, entre les deux et cinq. 

Six est le prochain non triés élément au tableau. Et en fait six est supérieur à cinq, afin on n'a même pas besoin de faire une permutation. Nous pouvons simplement virer à droite sur six l'extrémité de la partie triés. 

Enfin, quatre est le dernier élément non triés. Donc, nous allons le mettre de côté, changement au cours du les éléments que nous avons besoin de passer plus, et ensuite mettre à quatre où il appartient. Et maintenant, regardez, nous avons en quelque sorte de tous les éléments. Remarquez avec insertion Trier, nous ne disposions pas pour aller d'avant en arrière à travers la matrice. Nous n'y sommes allés à travers la matrice un moment, et nous avons déplacé les choses que nous avions déjà rencontré, dans l'ordre pour faire place à des nouveaux éléments. 

Alors, quel est le pire des cas scénario avec le tri par insertion? Dans le pire des cas, le tableau est dans l'ordre inverse. Vous avez à déplacer chacun des n éléments jusqu'à n positions, chaque fois que nous avons de faire une insertion. Cela fait beaucoup de décalage. 

Dans le meilleur des cas, la tableau est parfaitement réglé. Et un peu comme ce qui est arrivé avec cinq et six dans l'exemple, où nous ne pouvions tout simplement virer sur sans avoir à faire tout déplacement, nous avions essentiellement le faisons. 

Si vous imaginez que notre tableau était de un à six, nous serions commençons par déclarant l'un est triée. Deux vient après un si nous pouvons simplement dire, OK, bien un et deux sont triés. Trois vient après deux oui, OK, un et deux et trois sont triés. 

Nous ne faisons pas des swaps, nous sommes de transférer cette ligne arbitraire triés et non triés entre que nous allons. Aussi efficacement que nous l'avons fait dans l'exemple, éléments virer au bleu, que nous procédons. Alors, quel est le pire des cas d'exécution, alors? Rappelez-vous, si nous devons passer chacun des les n éléments éventuellement n positions, Espérons que cela vous donne une idée que le pire des cas runtime est de Big O n carré. 

Si le tableau est parfaitement trié, tout ce que nous avons à faire est de regarder chaque élément une fois, et puis nous avons terminé. Donc, dans le meilleur des cas, il est l'oméga de n. 

Je suis Doug Lloyd. Ceci est CS50.