1 00:00:00,000 --> 00:00:03,360 >> [Jouer de la musique] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD: Très bien, alors tri à bulles est un algorithme 4 00:00:06,730 --> 00:00:08,730 vous pouvez utiliser pour trier un ensemble d'éléments. 5 00:00:08,730 --> 00:00:10,850 Jetons un regard sur la façon dont cela fonctionne. 6 00:00:10,850 --> 00:00:13,240 >> Donc, l'idée de base derrière tri à bulles est la suivante. 7 00:00:13,240 --> 00:00:17,340 Nous voulons généralement se déplacer plus haut éléments évalués généralement à la droite, 8 00:00:17,340 --> 00:00:20,340 et abaisser éléments évalués général à gauche, que nous pourrions nous attendre. 9 00:00:20,340 --> 00:00:23,256 Nous voulons que les choses soient à la baisse le début, et les choses plus élevées 10 00:00:23,256 --> 00:00:24,970 être à la fin. 11 00:00:24,970 --> 00:00:26,130 >> Comment faisons-nous cela? 12 00:00:26,130 --> 00:00:28,040 Eh bien dans le code de pseudo-code, nous pourrions dire, de laisser 13 00:00:28,040 --> 00:00:30,320 initialiser un compteur de swap à une valeur non nulle. 14 00:00:30,320 --> 00:00:32,570 Nous verrons pourquoi nous faisons ce que dans une seconde. 15 00:00:32,570 --> 00:00:36,090 Et puis nous répétons le suivant processus jusqu'à ce que le compteur de swap est 0, 16 00:00:36,090 --> 00:00:39,910 ou jusqu'à ce que nous ne faisons aucune swaps à tous. 17 00:00:39,910 --> 00:00:43,170 >> Réinitialiser le compteur de swap à 0 si elle est pas déjà 0. 18 00:00:43,170 --> 00:00:46,420 Ensuite, regardez à chaque paire d'éléments adjacents. 19 00:00:46,420 --> 00:00:49,550 Si ces deux éléments sont pas dans l'ordre, les échanger, 20 00:00:49,550 --> 00:00:51,620 et ajouter 1 au compteur de swap. 21 00:00:51,620 --> 00:00:53,870 Si vous songez à ceci avant que vous visualisez, 22 00:00:53,870 --> 00:00:57,471 notez que cela va se déplacer plus bas éléments évalués à la gauche 23 00:00:57,471 --> 00:01:00,720 et des éléments vers la droite plus grande valeur, faire efficacement ce que nous voulons faire, 24 00:01:00,720 --> 00:01:03,940 qui est déplacer les groupes des éléments de cette façon. 25 00:01:03,940 --> 00:01:07,035 Voyons voir comment cela se pourrait ressembler à l'aide de notre gamme 26 00:01:07,035 --> 00:01:10,504 que nous avons utilisé pour tester ces algorithmes. 27 00:01:10,504 --> 00:01:13,420 Nous avons un tableau non trié ici encore, indiqué par l'ensemble des éléments 28 00:01:13,420 --> 00:01:14,840 étant en rouge. 29 00:01:14,840 --> 00:01:17,970 Je tournai ma échange contre à une valeur non nulle. 30 00:01:17,970 --> 00:01:20,610 Je choisis arbitrairement négative 1-- il est pas 0. 31 00:01:20,610 --> 00:01:23,840 Nous voulons répéter ce processus jusqu'à ce que le compteur de swap est 0. 32 00:01:23,840 --> 00:01:26,540 Voilà pourquoi je mis mon échange compteur à une valeur différente de zéro, 33 00:01:26,540 --> 00:01:29,400 car sinon le échange serait contre 0. 34 00:01:29,400 --> 00:01:31,610 Nous serions même pas commencer la Procédé de l'algorithme. 35 00:01:31,610 --> 00:01:33,610 Encore une fois, les étapes soient: réinitialiser le compteur de swap 36 00:01:33,610 --> 00:01:37,900 à 0, puis regardez à chaque adjacente paire, et si elles sont hors d'usage, 37 00:01:37,900 --> 00:01:40,514 les échanger, et ajouter 1 au comptoir d'échange. 38 00:01:40,514 --> 00:01:41,680 Donc, nous allons commencer ce processus. 39 00:01:41,680 --> 00:01:44,430 Donc la première chose que nous faisons est nous avons mis le compteur de swap à 0, 40 00:01:44,430 --> 00:01:46,660 et puis nous commençons à regarder à chaque paire adjacente. 41 00:01:46,660 --> 00:01:49,140 >> Nous commençons donc regarder d'abord 5 et 2. 42 00:01:49,140 --> 00:01:52,410 Nous voyons qu'ils sont hors de l'ordre et donc nous les échangeons. 43 00:01:52,410 --> 00:01:53,830 Et nous ajoutons 1 au compteur de swap. 44 00:01:53,830 --> 00:01:57,860 Alors maintenant, notre compteur de swap est 1, et 2 et 5 ont été commuté. 45 00:01:57,860 --> 00:01:59,370 Maintenant, nous le répétons à nouveau le processus. 46 00:01:59,370 --> 00:02:03,540 >> Nous attendons à la prochaine paire adjacente, 5 et 1-- ils sont également de l'ordre, 47 00:02:03,540 --> 00:02:06,960 donc nous les échangeons et nous ajoutons 1 au compteur de swap. 48 00:02:06,960 --> 00:02:08,900 Ensuite, nous regardons 5 et 3. 49 00:02:08,900 --> 00:02:13,830 Ils sont hors d'usage, de sorte que nous échanger eux et nous ajouter 1 au compteur de swap. 50 00:02:13,830 --> 00:02:15,550 Ensuite, nous regardons 5 et 6. 51 00:02:15,550 --> 00:02:18,630 Ils sont dans l'ordre, de sorte que nous ne le font pas en fait besoin d'échanger quoi que ce soit cette fois. 52 00:02:18,630 --> 00:02:20,250 Ensuite, nous regardons 6 et 4. 53 00:02:20,250 --> 00:02:24,920 Ils sont également de l'ordre, de sorte que nous échanger eux et nous ajouter 1 au compteur de swap. 54 00:02:24,920 --> 00:02:26,230 >> Maintenant, remarquez ce qui est arrivé. 55 00:02:26,230 --> 00:02:29,514 Nous avons déménagé 6 tout le chemin jusqu'à la fin. 56 00:02:29,514 --> 00:02:32,180 Donc, dans la sélection sorte, si vous avez vu que la vidéo, ce que nous avons fait était 57 00:02:32,180 --> 00:02:35,290 nous avons fini par déplacer le plus petits éléments dans le bâtiment 58 00:02:35,290 --> 00:02:39,640 le tableau trié essentiellement de de gauche à droite, petit au plus grand. 59 00:02:39,640 --> 00:02:43,200 Dans le cas du tri à bulles, si nous sommes suivant cet algorithme particulier, 60 00:02:43,200 --> 00:02:46,720 nous allons en fait être la construction le tableau trié de droite 61 00:02:46,720 --> 00:02:49,100 à gauche, le plus grand au plus petit. 62 00:02:49,100 --> 00:02:53,840 Nous avons effectivement barboter 6, le plus grande valeur, tout le chemin jusqu'à la fin. 63 00:02:53,840 --> 00:02:56,165 >> Et donc nous pouvons maintenant déclarer ce qui est trié, 64 00:02:56,165 --> 00:02:59,130 et à l'avenir iterations-- en passant par le tableau again-- 65 00:02:59,130 --> 00:03:01,280 nous ne devons considérer 6 plus. 66 00:03:01,280 --> 00:03:03,850 Nous avons seulement à considérer les éléments non triés 67 00:03:03,850 --> 00:03:06,299 quand nous nous penchons sur les paires adjacentes. 68 00:03:06,299 --> 00:03:08,340 Donc, nous avons terminé un passer par tri à bulles. 69 00:03:08,340 --> 00:03:11,941 Alors maintenant, nous allons revenir à la question, répéter jusqu'à ce que le compteur de swap est 0. 70 00:03:11,941 --> 00:03:13,690 Eh bien le compteur de swap est de 4, donc nous allons 71 00:03:13,690 --> 00:03:15,410 de répéter à nouveau ce processus. 72 00:03:15,410 --> 00:03:19,180 >> Nous allons réinitialiser le compteur de swap à 0, et de regarder chaque paire adjacente. 73 00:03:19,180 --> 00:03:21,890 Nous commençons donc par 2 et ils sont 1-- sur ordre, de sorte que nous les échanger 74 00:03:21,890 --> 00:03:23,620 et nous ajoutons 1 au compteur de swap. 75 00:03:23,620 --> 00:03:25,490 2 et 3, ils sont dans l'ordre. 76 00:03:25,490 --> 00:03:27,060 On n'a pas besoin de faire quoi que ce soit. 77 00:03:27,060 --> 00:03:28,420 3 et 5 sont dans l'ordre. 78 00:03:28,420 --> 00:03:30,150 On n'a pas besoin de faire quelque chose là-bas. 79 00:03:30,150 --> 00:03:32,515 >> 5 et 4, ils sont hors de l'ordre, et nous 80 00:03:32,515 --> 00:03:35,130 besoin de les échanger et d'ajouter 1 au compteur de swap. 81 00:03:35,130 --> 00:03:38,880 Et maintenant, nous avons déplacé 5, le prochain élément le plus important, 82 00:03:38,880 --> 00:03:40,920 à l'extrémité de la partie non triés. 83 00:03:40,920 --> 00:03:44,360 Donc, nous pouvons maintenant appeler ça partie de la portion triés. 84 00:03:44,360 --> 00:03:47,180 >> Maintenant, vous êtes à la recherche à la écran et ne peut probablement dire, 85 00:03:47,180 --> 00:03:50,130 que puis-je, que le tableau est trié en ce moment. 86 00:03:50,130 --> 00:03:51,820 Mais nous ne pouvons pas prouver encore que. 87 00:03:51,820 --> 00:03:54,359 Nous ne disposons pas une garantie qu'il est triée. 88 00:03:54,359 --> 00:03:56,900 Mais ceci est où le swap compteur va entrer en jeu. 89 00:03:56,900 --> 00:03:59,060 >> Donc, nous avons complété une passe. 90 00:03:59,060 --> 00:04:00,357 Le compteur de swap est 2. 91 00:04:00,357 --> 00:04:02,190 Donc, nous allons répéter ce processus nouveau, 92 00:04:02,190 --> 00:04:04,290 répéter jusqu'à ce que le compteur de swap est 0. 93 00:04:04,290 --> 00:04:05,550 Réinitialiser le compteur de swap à 0. 94 00:04:05,550 --> 00:04:06,820 Donc, nous allons réinitialiser. 95 00:04:06,820 --> 00:04:09,810 >> Maintenant, regardez chaque paire adjacente. 96 00:04:09,810 --> 00:04:11,880 Voilà dans l'ordre, 1 et 2. 97 00:04:11,880 --> 00:04:13,590 2 et 3 sont dans l'ordre. 98 00:04:13,590 --> 00:04:15,010 3 et 4 sont dans l'ordre. 99 00:04:15,010 --> 00:04:19,250 Donc, à ce stade, nous remarquons avons terminé en regardant chaque paire adjacente, 100 00:04:19,250 --> 00:04:22,530 mais le compteur de swap est toujours 0. 101 00:04:22,530 --> 00:04:25,520 >> Si nous ne devons pas passer tous les éléments, puis ils 102 00:04:25,520 --> 00:04:28,340 doit être en ordre, par Grâce à ce procédé. 103 00:04:28,340 --> 00:04:32,000 Et donc une efficacité de toutes sortes, que les informaticiens de nous aimons, 104 00:04:32,000 --> 00:04:35,560 est, nous pouvons maintenant déclarons l'ensemble du réseau doit 105 00:04:35,560 --> 00:04:38,160 être triés, parce que nous ne avoir à échanger des éléments. 106 00:04:38,160 --> 00:04:40,380 Voilà assez agréable. 107 00:04:40,380 --> 00:04:43,260 >> Alors, quel est le pire des cas scénario avec tri à bulles? 108 00:04:43,260 --> 00:04:46,240 Dans le pire des cas, le tableau est afin complètement inverse, 109 00:04:46,240 --> 00:04:49,870 et nous avons donc à chaque bulle les grands éléments de l'ensemble 110 00:04:49,870 --> 00:04:51,780 le chemin à travers le réseau. 111 00:04:51,780 --> 00:04:55,350 Et nous devons aussi efficace bulle tous les petits éléments de retour 112 00:04:55,350 --> 00:04:57,050 tout le chemin à travers la matrice, aussi. 113 00:04:57,050 --> 00:05:01,950 Donc, chacun des n éléments a de se déplacer dans tous les autres n éléments. 114 00:05:01,950 --> 00:05:04,102 Voilà donc le pire des cas. 115 00:05:04,102 --> 00:05:05,810 Dans le meilleur des cas scénario bien, cela est 116 00:05:05,810 --> 00:05:07,880 légèrement différente de la sélection sorte. 117 00:05:07,880 --> 00:05:10,040 Le tableau est déjà triés quand nous allons dans. 118 00:05:10,040 --> 00:05:12,550 Nous ne devons faire aucune swaps sur la première passe. 119 00:05:12,550 --> 00:05:14,940 Donc, nous pourrions avoir à regarder au moins d'éléments, non? 120 00:05:14,940 --> 00:05:18,580 Nous ne devons pas répéter cette traiter un certain nombre de fois. 121 00:05:18,580 --> 00:05:19,540 >> donc, qu'est-ce que ça veut dire? 122 00:05:19,540 --> 00:05:22,390 Alors, quel est le pire des cas pour bubble sort, et ce qui est 123 00:05:22,390 --> 00:05:25,330 le meilleur scénario pour tri à bulles? 124 00:05:25,330 --> 00:05:27,770 Avez-vous deviné cela? 125 00:05:27,770 --> 00:05:32,420 Dans le pire des cas, vous devez itérer sur l'ensemble des n éléments de n fois. 126 00:05:32,420 --> 00:05:34,220 Donc le pire des cas est n carré. 127 00:05:34,220 --> 00:05:36,550 >> Si le tableau est parfaitement triée cependant, vous ne 128 00:05:36,550 --> 00:05:38,580 avoir à regarder à chaque des éléments une fois. 129 00:05:38,580 --> 00:05:42,670 Et si le compteur de swap est toujours 0, vous pouvez dire que ce tableau est trié. 130 00:05:42,670 --> 00:05:45,780 Et donc dans le meilleur des cas, cela est fait mieux que la sélection 131 00:05:45,780 --> 00:05:49,230 sort-- il est l'oméga de n. 132 00:05:49,230 --> 00:05:50,270 >> Je suis Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Ceci est CS50. 134 00:05:52,140 --> 00:05:54,382