[За възпроизвеждане на музика] Дъг LLOYD: Добре де, метод на мехурчето е един алгоритъм можете да използвате, за да сортирате набор от елементи. Нека да видим как тя работи. 

Така че основната идея метод на мехурчето е това. Ние обикновено искат да се преместят по-висока уважаеми елементи принцип на правото, и по-ниски оценяват елементи като цяло наляво, както бихме очаквали. Искаме долните неща, за да бъде най- началото, и по-висшите неща да бъде в края. 

Как правим това? Ами в Псевдокод код, бихме могли да кажем, нека задаване на суап в противоречие с ненулева стойност. Ще видим защо правим, че в секунда. И тогава ние повтаряме следното процес, докато броячът суап е 0, или докато ние не правим никакви суапове на всички. 

Нулирайте брояча да суап 0 ако не е вече 0. След това погледнете всеки съседна двойка елементи. Ако тези два елемента са които не са в ред, да ги сменяте, и се добавя 1 до щанда за размяна. Ако си мислиш за това преди да го визуализира, забележите, че това ще се придвижи по-ниско уважаеми елементи от ляво и по-високо ценен елементи на правото, ефективно прави това, което искаме да направим, който се движи тези групи на елементите в този начин. Нека да се визуализира как това може да изглежда като използвате нашата масив че се използва за тестване тези алгоритми. Имаме сортиран масив тук отново, посочено от всички елементи е в червено. И аз поставям суап брояч да ненулева стойност. Аз избрах произволно отрицателна 1-- това не е 0. Искаме да повторите този процес докато броячът суап е 0. Ето защо аз поставям суап в противоречие с някои ненулева стойност, защото в противен случай суап брояч ще бъде 0. Ние дори не започва да тече от процес на алгоритъма. Така че отново, стъпките are-- нулира брояча суап 0, след това погледнете всяка съседна чифт, и ако те не са на ред, ги разменят, и добавете 1 до щанда за размяна. Така че нека да започнем този процес. Така че първото нещо, което правим, е тръгнахме тезгяха суап до 0, и тогава започнете да търсите при всяка съседна двойка. 

Така че ние първо да започнат да търсят при 5 и 2. Ние виждаме, че те са изложени на поръчка и затова ние ги разменят. И ние добавяме 1 до щанда за размяна. Така че сега нашата суап брояч е 1, и 2 и 5 са ​​включен. Сега повторете процеса отново. 

Очакваме в следващата съседна двойка, 5 и 1-- те са също в ред, така че ние ги разменят и да добавите 1 до щанда за размяна. Тогава ние гледаме на 5 и 3. Те са в ред, за да можем да сменяте тях и ние добавяме 1 до щанда за размяна. Тогава ние гледаме на 5 и 6. Те са в ред, така че ние всъщност не Трябва да сменяте нещо този път. Тогава ние гледаме на 6 и 4. Освен това те са в ред, за да можем да сменяте тях и ние добавяме 1 до щанда за размяна. 

Сега забележи какво се е случило. Ние се преместих 6 целия път до края. Така че при избора на вид, ако сте Вижда се, че видеото, което направихме беше ние в крайна сметка преместване на най-малките елементи в сграда сортирания масив по същество от ляво на дясно, най-малкия до най-големия. В случая на метод на мехурчето, ако сме след този конкретен алгоритъм, ние всъщност ще бъде изграждането на сортирания масив от дясно наляво, най-големия до най-малкия. Ние ефективно разпенва 6 г. най-голямата стойност, по целия път до края. 

И така, сега можем да декларираме че това се сортират, и в бъдеще iterations-- преминава през масива again-- ние не трябва да се помисли за 6 вече. Ние само трябва да се помисли на несортиран елементи когато гледаме съседни двойки. Така че ние имаме един завършен мине през балон подреди. Така че сега се върнем на въпроса, повтаря, докато броячът суап е 0. Ами тезгяха суап е 4, така че отиваме да продължават да повтарят този процес отново. 

Отиваме да нулирате брояча суап до 0, и гледам на всяка съседна двойка. Така че ние започваме с 2 и 1-- те са в ред, за да можем да ги сменяте и ние добавяме 1 до щанда за размяна. 2 и 3, те са в ред. Ние не трябва да правите нищо. 3 и 5 са ​​в ред. Ние не трябва да правите нищо там. 

5 и 4, те са изложени на реда, така и ние Трябва да ги разменят и да добавите 1 до щанда за размяна. И сега ние се преместих 5, следващия по големина елемент, до края на несортиран част. Така че сега можем да наречем, че част от сортирани част. 

Сега, което търсите в екран и вероятно може да каже, както мога, че масивът се сортират в момента. Но не можем да докажем, че все още. Ние не разполагаме с гаранция че това е сортирани. Но това е мястото, където суапа брояч ще влезе в игра. 

Така че ние сме завършили пас. Броячът на суап е 2. Така че ние ще повторя този процес отново, повтаря, докато броячът суап е 0. Нулира брояча за размяна на 0. Така че ние ще го изчисти. 

Сега погледнете всяка съседна двойка. Това е с цел, 1 и 2. 2 и 3 са в ред. 3 и 4 са в ред. Така че в този момент, забележете, като приключим гледаш всяка съседна двойка, но тезгяха суап все още е 0. 

Ако ние не трябва да превключите всички елементи, тогава трябва да е в ред, като силата на този процес. И така на ефективността на видове, че ние компютърните специалисти обичат, сега можем да декларираме целият масив мъст се сортира, защото ние не го направи Трябва да сменяте всички елементи. Това е доста приятно. 

Така че това, което е най-лошия случай сценарий с балон подреди? В най-лошия случай е масив в напълно обратен ред, и затова трябва да се балон всеки на всички големи елементи Между другото в масива. И ние ефективно също така трябва да балон всички малки елементи назад чак в масива, също. Така всеки от N елементите трябва да се движи във всички от останалите N елементи. Така че това е най-лошия сценарий. В най-добрия случай сценарий обаче, това е малко по-различен от селекция подреди. Масивът вече сортирани когато отидем инча Ние не трябва да се прави всяка суапове за първото преминаване. Така че ние може да видя най-малко елементи, нали? Ние не трябва да се повтаря това обработват няколко пъти повече. 

И така, какво означава това? Така че това, което е най-лошият сценарий за метод на мехурчето, и това, което е най-добрият сценарий за метод на мехурчето? Знаете ли, предполагам, че това? В най-лошия случай ще трябва да превъртите във всички елементи н н времената на. Така че най-лошия случай е п квадрат. 

Ако матрицата е напълно сортирани че, вие само Трябва да гледаме на всеки на елементите веднъж. И ако броячът суап все още е 0, може да се каже този масив се сортира. И така, в най-добрия случай, това е всъщност по-добре от селекция sort-- това е омега от п. 

Аз съм Дъг Лойд. Това е CS50.