[Jouer de la musique] DOUG LLOYD: Très bien, alors tri à bulles est un algorithme vous pouvez utiliser pour trier un ensemble d'éléments. Jetons un regard sur la façon dont cela fonctionne. 

Donc, l'idée de base derrière tri à bulles est la suivante. Nous voulons généralement se déplacer plus haut éléments évalués généralement à la droite, et abaisser éléments évalués général à gauche, que nous pourrions nous attendre. Nous voulons que les choses soient à la baisse le début, et les choses plus élevées être à la fin. 

Comment faisons-nous cela? Eh bien dans le code de pseudo-code, nous pourrions dire, de laisser initialiser un compteur de swap à une valeur non nulle. Nous verrons pourquoi nous faisons ce que dans une seconde. Et puis nous répétons le suivant processus jusqu'à ce que le compteur de swap est 0, ou jusqu'à ce que nous ne faisons aucune swaps à tous. 

Réinitialiser le compteur de swap à 0 si elle est pas déjà 0. Ensuite, regardez à chaque paire d'éléments adjacents. Si ces deux éléments sont pas dans l'ordre, les échanger, et ajouter 1 au compteur de swap. Si vous songez à ceci avant que vous visualisez, notez que cela va se déplacer plus bas éléments évalués à la gauche et des éléments vers la droite plus grande valeur, faire efficacement ce que nous voulons faire, qui est déplacer les groupes des éléments de cette façon. Voyons voir comment cela se pourrait ressembler à l'aide de notre gamme que nous avons utilisé pour tester ces algorithmes. Nous avons un tableau non trié ici encore, indiqué par l'ensemble des éléments étant en rouge. Je tournai ma échange contre à une valeur non nulle. Je choisis arbitrairement négative 1-- il est pas 0. Nous voulons répéter ce processus jusqu'à ce que le compteur de swap est 0. Voilà pourquoi je mis mon échange compteur à une valeur différente de zéro, car sinon le échange serait contre 0. Nous serions même pas commencer la Procédé de l'algorithme. Encore une fois, les étapes soient: réinitialiser le compteur de swap à 0, puis regardez à chaque adjacente paire, et si elles sont hors d'usage, les échanger, et ajouter 1 au comptoir d'échange. Donc, nous allons commencer ce processus. Donc la première chose que nous faisons est nous avons mis le compteur de swap à 0, et puis nous commençons à regarder à chaque paire adjacente. 

Nous commençons donc regarder d'abord 5 et 2. Nous voyons qu'ils sont hors de l'ordre et donc nous les échangeons. Et nous ajoutons 1 au compteur de swap. Alors maintenant, notre compteur de swap est 1, et 2 et 5 ont été commuté. Maintenant, nous le répétons à nouveau le processus. 

Nous attendons à la prochaine paire adjacente, 5 et 1-- ils sont également de l'ordre, donc nous les échangeons et nous ajoutons 1 au compteur de swap. Ensuite, nous regardons 5 et 3. Ils sont hors d'usage, de sorte que nous échanger eux et nous ajouter 1 au compteur de swap. Ensuite, nous regardons 5 et 6. Ils sont dans l'ordre, de sorte que nous ne le font pas en fait besoin d'échanger quoi que ce soit cette fois. Ensuite, nous regardons 6 et 4. Ils sont également de l'ordre, de sorte que nous échanger eux et nous ajouter 1 au compteur de swap. 

Maintenant, remarquez ce qui est arrivé. Nous avons déménagé 6 tout le chemin jusqu'à la fin. Donc, dans la sélection sorte, si vous avez vu que la vidéo, ce que nous avons fait était nous avons fini par déplacer le plus petits éléments dans le bâtiment le tableau trié essentiellement de de gauche à droite, petit au plus grand. Dans le cas du tri à bulles, si nous sommes suivant cet algorithme particulier, nous allons en fait être la construction le tableau trié de droite à gauche, le plus grand au plus petit. Nous avons effectivement barboter 6, le plus grande valeur, tout le chemin jusqu'à la fin. 

Et donc nous pouvons maintenant déclarer ce qui est trié, et à l'avenir iterations-- en passant par le tableau again-- nous ne devons considérer 6 plus. Nous avons seulement à considérer les éléments non triés quand nous nous penchons sur les paires adjacentes. Donc, nous avons terminé un passer par tri à bulles. Alors maintenant, nous allons revenir à la question, répéter jusqu'à ce que le compteur de swap est 0. Eh bien le compteur de swap est de 4, donc nous allons de répéter à nouveau ce processus. 

Nous allons réinitialiser le compteur de swap à 0, et de regarder chaque paire adjacente. Nous commençons donc par 2 et ils sont 1-- sur ordre, de sorte que nous les échanger et nous ajoutons 1 au compteur de swap. 2 et 3, ils sont dans l'ordre. On n'a pas besoin de faire quoi que ce soit. 3 et 5 sont dans l'ordre. On n'a pas besoin de faire quelque chose là-bas. 

5 et 4, ils sont hors de l'ordre, et nous besoin de les échanger et d'ajouter 1 au compteur de swap. Et maintenant, nous avons déplacé 5, le prochain élément le plus important, à l'extrémité de la partie non triés. Donc, nous pouvons maintenant appeler ça partie de la portion triés. 

Maintenant, vous êtes à la recherche à la écran et ne peut probablement dire, que puis-je, que le tableau est trié en ce moment. Mais nous ne pouvons pas prouver encore que. Nous ne disposons pas une garantie qu'il est triée. Mais ceci est où le swap compteur va entrer en jeu. 

Donc, nous avons complété une passe. Le compteur de swap est 2. Donc, nous allons répéter ce processus nouveau, répéter jusqu'à ce que le compteur de swap est 0. Réinitialiser le compteur de swap à 0. Donc, nous allons réinitialiser. 

Maintenant, regardez chaque paire adjacente. Voilà dans l'ordre, 1 et 2. 2 et 3 sont dans l'ordre. 3 et 4 sont dans l'ordre. Donc, à ce stade, nous remarquons avons terminé en regardant chaque paire adjacente, mais le compteur de swap est toujours 0. 

Si nous ne devons pas passer tous les éléments, puis ils doit être en ordre, par Grâce à ce procédé. Et donc une efficacité de toutes sortes, que les informaticiens de nous aimons, est, nous pouvons maintenant déclarons l'ensemble du réseau doit être triés, parce que nous ne avoir à échanger des éléments. Voilà assez agréable. 

Alors, quel est le pire des cas scénario avec tri à bulles? Dans le pire des cas, le tableau est afin complètement inverse, et nous avons donc à chaque bulle les grands éléments de l'ensemble le chemin à travers le réseau. Et nous devons aussi efficace bulle tous les petits éléments de retour tout le chemin à travers la matrice, aussi. Donc, chacun des n éléments a de se déplacer dans tous les autres n éléments. Voilà donc le pire des cas. Dans le meilleur des cas scénario bien, cela est légèrement différente de la sélection sorte. Le tableau est déjà triés quand nous allons dans. Nous ne devons faire aucune swaps sur la première passe. Donc, nous pourrions avoir à regarder au moins d'éléments, non? Nous ne devons pas répéter cette traiter un certain nombre de fois. 

donc, qu'est-ce que ça veut dire? Alors, quel est le pire des cas pour bubble sort, et ce qui est le meilleur scénario pour tri à bulles? Avez-vous deviné cela? Dans le pire des cas, vous devez itérer sur l'ensemble des n éléments de n fois. Donc le pire des cas est n carré. 

Si le tableau est parfaitement triée cependant, vous ne avoir à regarder à chaque des éléments une fois. Et si le compteur de swap est toujours 0, vous pouvez dire que ce tableau est trié. Et donc dans le meilleur des cas, cela est fait mieux que la sélection sort-- il est l'oméga de n. 

Je suis Doug Lloyd. Ceci est CS50.