1 00:00:00,000 --> 00:00:03,360 >> [За възпроизвеждане на музика] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 Дъг LLOYD: Добре де, метод на мехурчето е един алгоритъм 4 00:00:06,730 --> 00:00:08,730 можете да използвате, за да сортирате набор от елементи. 5 00:00:08,730 --> 00:00:10,850 Нека да видим как тя работи. 6 00:00:10,850 --> 00:00:13,240 >> Така че основната идея метод на мехурчето е това. 7 00:00:13,240 --> 00:00:17,340 Ние обикновено искат да се преместят по-висока уважаеми елементи принцип на правото, 8 00:00:17,340 --> 00:00:20,340 и по-ниски оценяват елементи като цяло наляво, както бихме очаквали. 9 00:00:20,340 --> 00:00:23,256 Искаме долните неща, за да бъде най- началото, и по-висшите неща 10 00:00:23,256 --> 00:00:24,970 да бъде в края. 11 00:00:24,970 --> 00:00:26,130 >> Как правим това? 12 00:00:26,130 --> 00:00:28,040 Ами в Псевдокод код, бихме могли да кажем, нека 13 00:00:28,040 --> 00:00:30,320 задаване на суап в противоречие с ненулева стойност. 14 00:00:30,320 --> 00:00:32,570 Ще видим защо правим, че в секунда. 15 00:00:32,570 --> 00:00:36,090 И тогава ние повтаряме следното процес, докато броячът суап е 0, 16 00:00:36,090 --> 00:00:39,910 или докато ние не правим никакви суапове на всички. 17 00:00:39,910 --> 00:00:43,170 >> Нулирайте брояча да суап 0 ако не е вече 0. 18 00:00:43,170 --> 00:00:46,420 След това погледнете всеки съседна двойка елементи. 19 00:00:46,420 --> 00:00:49,550 Ако тези два елемента са които не са в ред, да ги сменяте, 20 00:00:49,550 --> 00:00:51,620 и се добавя 1 до щанда за размяна. 21 00:00:51,620 --> 00:00:53,870 Ако си мислиш за това преди да го визуализира, 22 00:00:53,870 --> 00:00:57,471 забележите, че това ще се придвижи по-ниско уважаеми елементи от ляво 23 00:00:57,471 --> 00:01:00,720 и по-високо ценен елементи на правото, ефективно прави това, което искаме да направим, 24 00:01:00,720 --> 00:01:03,940 който се движи тези групи на елементите в този начин. 25 00:01:03,940 --> 00:01:07,035 Нека да се визуализира как това може да изглежда като използвате нашата масив 26 00:01:07,035 --> 00:01:10,504 че се използва за тестване тези алгоритми. 27 00:01:10,504 --> 00:01:13,420 Имаме сортиран масив тук отново, посочено от всички елементи 28 00:01:13,420 --> 00:01:14,840 е в червено. 29 00:01:14,840 --> 00:01:17,970 И аз поставям суап брояч да ненулева стойност. 30 00:01:17,970 --> 00:01:20,610 Аз избрах произволно отрицателна 1-- това не е 0. 31 00:01:20,610 --> 00:01:23,840 Искаме да повторите този процес докато броячът суап е 0. 32 00:01:23,840 --> 00:01:26,540 Ето защо аз поставям суап в противоречие с някои ненулева стойност, 33 00:01:26,540 --> 00:01:29,400 защото в противен случай суап брояч ще бъде 0. 34 00:01:29,400 --> 00:01:31,610 Ние дори не започва да тече от процес на алгоритъма. 35 00:01:31,610 --> 00:01:33,610 Така че отново, стъпките are-- нулира брояча суап 36 00:01:33,610 --> 00:01:37,900 0, след това погледнете всяка съседна чифт, и ако те не са на ред, 37 00:01:37,900 --> 00:01:40,514 ги разменят, и добавете 1 до щанда за размяна. 38 00:01:40,514 --> 00:01:41,680 Така че нека да започнем този процес. 39 00:01:41,680 --> 00:01:44,430 Така че първото нещо, което правим, е тръгнахме тезгяха суап до 0, 40 00:01:44,430 --> 00:01:46,660 и тогава започнете да търсите при всяка съседна двойка. 41 00:01:46,660 --> 00:01:49,140 >> Така че ние първо да започнат да търсят при 5 и 2. 42 00:01:49,140 --> 00:01:52,410 Ние виждаме, че те са изложени на поръчка и затова ние ги разменят. 43 00:01:52,410 --> 00:01:53,830 И ние добавяме 1 до щанда за размяна. 44 00:01:53,830 --> 00:01:57,860 Така че сега нашата суап брояч е 1, и 2 и 5 са ​​включен. 45 00:01:57,860 --> 00:01:59,370 Сега повторете процеса отново. 46 00:01:59,370 --> 00:02:03,540 >> Очакваме в следващата съседна двойка, 5 и 1-- те са също в ред, 47 00:02:03,540 --> 00:02:06,960 така че ние ги разменят и да добавите 1 до щанда за размяна. 48 00:02:06,960 --> 00:02:08,900 Тогава ние гледаме на 5 и 3. 49 00:02:08,900 --> 00:02:13,830 Те са в ред, за да можем да сменяте тях и ние добавяме 1 до щанда за размяна. 50 00:02:13,830 --> 00:02:15,550 Тогава ние гледаме на 5 и 6. 51 00:02:15,550 --> 00:02:18,630 Те са в ред, така че ние всъщност не Трябва да сменяте нещо този път. 52 00:02:18,630 --> 00:02:20,250 Тогава ние гледаме на 6 и 4. 53 00:02:20,250 --> 00:02:24,920 Освен това те са в ред, за да можем да сменяте тях и ние добавяме 1 до щанда за размяна. 54 00:02:24,920 --> 00:02:26,230 >> Сега забележи какво се е случило. 55 00:02:26,230 --> 00:02:29,514 Ние се преместих 6 целия път до края. 56 00:02:29,514 --> 00:02:32,180 Така че при избора на вид, ако сте Вижда се, че видеото, което направихме беше 57 00:02:32,180 --> 00:02:35,290 ние в крайна сметка преместване на най-малките елементи в сграда 58 00:02:35,290 --> 00:02:39,640 сортирания масив по същество от ляво на дясно, най-малкия до най-големия. 59 00:02:39,640 --> 00:02:43,200 В случая на метод на мехурчето, ако сме след този конкретен алгоритъм, 60 00:02:43,200 --> 00:02:46,720 ние всъщност ще бъде изграждането на сортирания масив от дясно 61 00:02:46,720 --> 00:02:49,100 наляво, най-големия до най-малкия. 62 00:02:49,100 --> 00:02:53,840 Ние ефективно разпенва 6 г. най-голямата стойност, по целия път до края. 63 00:02:53,840 --> 00:02:56,165 >> И така, сега можем да декларираме че това се сортират, 64 00:02:56,165 --> 00:02:59,130 и в бъдеще iterations-- преминава през масива again-- 65 00:02:59,130 --> 00:03:01,280 ние не трябва да се помисли за 6 вече. 66 00:03:01,280 --> 00:03:03,850 Ние само трябва да се помисли на несортиран елементи 67 00:03:03,850 --> 00:03:06,299 когато гледаме съседни двойки. 68 00:03:06,299 --> 00:03:08,340 Така че ние имаме един завършен мине през балон подреди. 69 00:03:08,340 --> 00:03:11,941 Така че сега се върнем на въпроса, повтаря, докато броячът суап е 0. 70 00:03:11,941 --> 00:03:13,690 Ами тезгяха суап е 4, така че отиваме 71 00:03:13,690 --> 00:03:15,410 да продължават да повтарят този процес отново. 72 00:03:15,410 --> 00:03:19,180 >> Отиваме да нулирате брояча суап до 0, и гледам на всяка съседна двойка. 73 00:03:19,180 --> 00:03:21,890 Така че ние започваме с 2 и 1-- те са в ред, за да можем да ги сменяте 74 00:03:21,890 --> 00:03:23,620 и ние добавяме 1 до щанда за размяна. 75 00:03:23,620 --> 00:03:25,490 2 и 3, те са в ред. 76 00:03:25,490 --> 00:03:27,060 Ние не трябва да правите нищо. 77 00:03:27,060 --> 00:03:28,420 3 и 5 са ​​в ред. 78 00:03:28,420 --> 00:03:30,150 Ние не трябва да правите нищо там. 79 00:03:30,150 --> 00:03:32,515 >> 5 и 4, те са изложени на реда, така и ние 80 00:03:32,515 --> 00:03:35,130 Трябва да ги разменят и да добавите 1 до щанда за размяна. 81 00:03:35,130 --> 00:03:38,880 И сега ние се преместих 5, следващия по големина елемент, 82 00:03:38,880 --> 00:03:40,920 до края на несортиран част. 83 00:03:40,920 --> 00:03:44,360 Така че сега можем да наречем, че част от сортирани част. 84 00:03:44,360 --> 00:03:47,180 >> Сега, което търсите в екран и вероятно може да каже, 85 00:03:47,180 --> 00:03:50,130 както мога, че масивът се сортират в момента. 86 00:03:50,130 --> 00:03:51,820 Но не можем да докажем, че все още. 87 00:03:51,820 --> 00:03:54,359 Ние не разполагаме с гаранция че това е сортирани. 88 00:03:54,359 --> 00:03:56,900 Но това е мястото, където суапа брояч ще влезе в игра. 89 00:03:56,900 --> 00:03:59,060 >> Така че ние сме завършили пас. 90 00:03:59,060 --> 00:04:00,357 Броячът на суап е 2. 91 00:04:00,357 --> 00:04:02,190 Така че ние ще повторя този процес отново, 92 00:04:02,190 --> 00:04:04,290 повтаря, докато броячът суап е 0. 93 00:04:04,290 --> 00:04:05,550 Нулира брояча за размяна на 0. 94 00:04:05,550 --> 00:04:06,820 Така че ние ще го изчисти. 95 00:04:06,820 --> 00:04:09,810 >> Сега погледнете всяка съседна двойка. 96 00:04:09,810 --> 00:04:11,880 Това е с цел, 1 и 2. 97 00:04:11,880 --> 00:04:13,590 2 и 3 са в ред. 98 00:04:13,590 --> 00:04:15,010 3 и 4 са в ред. 99 00:04:15,010 --> 00:04:19,250 Така че в този момент, забележете, като приключим гледаш всяка съседна двойка, 100 00:04:19,250 --> 00:04:22,530 но тезгяха суап все още е 0. 101 00:04:22,530 --> 00:04:25,520 >> Ако ние не трябва да превключите всички елементи, тогава 102 00:04:25,520 --> 00:04:28,340 трябва да е в ред, като силата на този процес. 103 00:04:28,340 --> 00:04:32,000 И така на ефективността на видове, че ние компютърните специалисти обичат, 104 00:04:32,000 --> 00:04:35,560 сега можем да декларираме целият масив мъст 105 00:04:35,560 --> 00:04:38,160 се сортира, защото ние не го направи Трябва да сменяте всички елементи. 106 00:04:38,160 --> 00:04:40,380 Това е доста приятно. 107 00:04:40,380 --> 00:04:43,260 >> Така че това, което е най-лошия случай сценарий с балон подреди? 108 00:04:43,260 --> 00:04:46,240 В най-лошия случай е масив в напълно обратен ред, 109 00:04:46,240 --> 00:04:49,870 и затова трябва да се балон всеки на всички големи елементи 110 00:04:49,870 --> 00:04:51,780 Между другото в масива. 111 00:04:51,780 --> 00:04:55,350 И ние ефективно също така трябва да балон всички малки елементи назад 112 00:04:55,350 --> 00:04:57,050 чак в масива, също. 113 00:04:57,050 --> 00:05:01,950 Така всеки от N елементите трябва да се движи във всички от останалите N елементи. 114 00:05:01,950 --> 00:05:04,102 Така че това е най-лошия сценарий. 115 00:05:04,102 --> 00:05:05,810 В най-добрия случай сценарий обаче, това е 116 00:05:05,810 --> 00:05:07,880 малко по-различен от селекция подреди. 117 00:05:07,880 --> 00:05:10,040 Масивът вече сортирани когато отидем инча 118 00:05:10,040 --> 00:05:12,550 Ние не трябва да се прави всяка суапове за първото преминаване. 119 00:05:12,550 --> 00:05:14,940 Така че ние може да видя най-малко елементи, нали? 120 00:05:14,940 --> 00:05:18,580 Ние не трябва да се повтаря това обработват няколко пъти повече. 121 00:05:18,580 --> 00:05:19,540 >> И така, какво означава това? 122 00:05:19,540 --> 00:05:22,390 Така че това, което е най-лошият сценарий за метод на мехурчето, и това, което е 123 00:05:22,390 --> 00:05:25,330 най-добрият сценарий за метод на мехурчето? 124 00:05:25,330 --> 00:05:27,770 Знаете ли, предполагам, че това? 125 00:05:27,770 --> 00:05:32,420 В най-лошия случай ще трябва да превъртите във всички елементи н н времената на. 126 00:05:32,420 --> 00:05:34,220 Така че най-лошия случай е п квадрат. 127 00:05:34,220 --> 00:05:36,550 >> Ако матрицата е напълно сортирани че, вие само 128 00:05:36,550 --> 00:05:38,580 Трябва да гледаме на всеки на елементите веднъж. 129 00:05:38,580 --> 00:05:42,670 И ако броячът суап все още е 0, може да се каже този масив се сортира. 130 00:05:42,670 --> 00:05:45,780 И така, в най-добрия случай, това е всъщност по-добре от селекция 131 00:05:45,780 --> 00:05:49,230 sort-- това е омега от п. 132 00:05:49,230 --> 00:05:50,270 >> Аз съм Дъг Лойд. 133 00:05:50,270 --> 00:05:52,140 Това е CS50. 134 00:05:52,140 --> 00:05:54,382