[Přehrávání hudby] DOUG LLOYD: Dobře, tak bublina třídění je algoritmus můžete použít řadit sadu prvků. Pojďme se podívat, jak to funguje. 

Takže základní myšlenka bubble sort je to. Obecně chceme přesunout vyšší ceněné prvky, obvykle na pravé straně, a nižší hodnotě prvky obecně doleva, jak bychom očekávali. Chceme, aby spodní věci byly v začátek, a vyšší věci být na konci. 

Jak to děláme? No v pseudokódu kódu, Dalo by se říci, pojďme nastavit počítadlo odkládací nenulovou hodnotu. Uvidíme, proč to děláme, že ve vteřině. A pak jsme zopakovat následující Proces, když čítač swap je 0, nebo dokud neděláme swapy vůbec. 

Vynulujte počítadlo odkládací 0, pokud to není už 0. Pak se podívejte na každý přilehlé dvojice prvků. Pokud se tyto dva prvky jsou není v pořádku, je vyměnit, a přidat 1 k pultu swapu. Pokud uvažujete o to dříve, než ho představit, Všimněte si, že to bude pohybovat nižší oceňují prvky vlevo a vyšší oceňují prvky vpravo, účinně dělat to, co chceme dělat, což je přesunout tyto skupiny prvků tímto způsobem. Pojďme si představit, jak to může vypadat pomocí naší nabídku že používá k testování out těchto algoritmů. Máme zde k netříděné pole znovu, označeny všechny prvky je v červené barvě. A obrátil jsem počítadlo odkládací na nenulovou hodnotu. I libovolně si vybral Negativní 1-- to není 0. Chceme, aby tento proces opakovat do pultu odkládacího 0. To je důvod, proč jsem nastavit svůj swapu v rozporu s nějakou nenulovou hodnotu, protože jinak odkládací pult by být 0. Neměli bychom ani začne běžet Způsob podle tohoto algoritmu. Takže znovu, kroky are-- vynulovat počítadlo odkládací na 0, pak se podívejte na každém přilehlý pair, a jestli jsou mimo provoz, je vyměnit, a přidat 1 k pultu swapu. Takže pojďme začít tento proces. Takže první věc, kterou děláme, je nastavíme čítač odkládací na 0, a pak začneme hledat v každé sousední dvojice. 

Tak jsme nejprve začít uvažovat o 5 a 2. Vidíme, že jsou mimo objednat a tak jsme je vyměnit. A přidáme 1 k pultu swapu. Takže teď náš čítač swap je 1, a 2 a 5 byly přepnut. Nyní jsme opět proces opakovat. 

Dívali jsme se na další sousední dvojice, 5 a 1-- jsou také mimo provoz, tak jsme je vyměnit a přidat 1 k pultu swapu. Pak se podíváme na 5 a 3. Jsou mimo provoz, takže jsme vyměnit je a přidáme 1 k pultu swapu. Pak se podíváme na 5 a 6. Jsou v pořádku, takže my vlastně je třeba vyměnit cokoliv tentokrát. Pak se podíváme na 6 a 4. Jsou také mimo provoz, takže jsme vyměnit je a přidáme 1 k pultu swapu. 

Teď si všimnout, co se stalo. Přesunuli jsme 6 celou cestu až do konce. Takže ve výběru druhu, pokud jste vidět, že video, co jsme udělali, bylo jsme skončili pohybem Nejmenší prvky v budově roztříděný pole v podstatě od zleva doprava, nejmenší k největší. V případě bublina druhu, když jsme po této konkrétní algoritmus, my vlastně bude stavět roztříděný pole zprava doleva, největší po nejmenší. Máme skutečně bublala 6, Největší hodnota, až do konce. 

A tak nyní můžeme prohlásit, že je tříděn, a v budoucnu iterations-- prochází pole again-- nemusíme uvažovat už 6. Máme jen zvážit netříděného prvky když se díváme na sousedních párů. Takže jsme skončili jeden projít bublina druhu. Takže teď se vrátíme k otázce, opakujte, dokud počítadlo swap je 0. No counter swapu je 4, takže jdeme aby znovu opakovat tento proces. 

Chystáme se vynulovat počítadlo odkládací na 0, a podívat se na každým sousedním párem. Takže začneme s 2 a 1-- jsou mimo provoz, takže jsme je vyměnit a přidáme 1 k pultu swapu. 2 a 3, jsou v pořádku. Nepotřebujeme nic dělat. 3 a 5 jsou v pořádku. Nepotřebujeme nic dělat tam. 

5 a 4, jsou mimo provoz, a tak jsme je třeba je vyměnit a přidat 1 k pultu swapu. A teď jsme se přestěhovali 5, Příští největší prvek, na konec netříděného části. Takže můžeme teď říkat, že část uspořádané části. 

Teď při pohledu na obrazovky a pravděpodobně může říct, jak můžu, že pole Je řazeny právě teď. Ale nemůžeme dokázat, že dosud. Nemáme záruku že je to třídit. Ale to je místo, kde swap Počítadlo to přijde do hry. 

Proto jsme dokončili a nahrává. Počítadlo swap je 2. Takže budeme opakovat se tento proces, opakujte, dokud počítadlo swap je 0. Vynulujte počitadlo odkládací 0. Takže my jej resetovat. 

Nyní se podívejte na každým sousedním párem. To je v pořádku, 1 a 2. 2 a 3 jsou v pořádku. 3 a 4 jsou v pořádku. Takže v tomto bodě, Všimněte si, že jsme dokončili při pohledu na každé sousední dvojice, ale počítadlo swap je stále 0. 

Pokud nebudeme muset přejít některé prvky, pak se musí být v pořádku tím, že Na základě tohoto procesu. A tak účinností druhů, Že jsme počítačoví odborníci milujeme, je nyní můžeme prohlásit, celé pole musí tříděny, protože jsme neměli muset vyměnit jakékoli prvky. To je docela pěkné. 

Takže to, co je nejhorší případ Scénář s bublinkové řazení? V nejhorším případě je pole ve zcela opačném pořadí, a proto musíme bublina každý velkých prvků all cestu přes pole. A my efektivně muset také bublina všech malých prvků zpět celou cestu přes pole, také. Takže každý z n elementy se musí pohybovat v rámci všech ostatních n elementy. Tak to je ten nejhorší možný scénář. V nejlepším případě scénář i když, je to mírně liší od výběru druhu. Pole je již řazeny když jdeme dovnitř. My nemusíme provádět žádné swapy na prvním průchodu. Takže možná budeme muset hledat na méně prvků, ne? My nemusíme opakovat zpracovat několikrát více než. 

Takže co to znamená? Takže to, co je nejhorší možný scénář k Bubble druhu, a to, co je nejlepší scénář pro bubble druhu? Věděli jste, že tohle? V nejhorším případě musíte iterovat napříč všemi n elementy n-krát. Takže nejhorší případ je n na druhou. 

V případě, že pole je dokonale tříděných i když, jen vy se podívat na sebe prvků jednou. A v případě, že počítadlo swap je stále 0, můžete říci toto pole je tříděn. A tak v nejlepším případě se jedná vlastně lepší než výběr sort-- to je omega n. 

Jsem Doug Lloyd. To je CS50.