[Prehrávanie hudby] DOUG LLOYD: Dobre, tak bublina triedenie je algoritmus môžete použiť radiť sadu prvkov. Poďme sa pozrieť, ako to funguje. 

Takže základná myšlienka bubble sort je to. Všeobecne chceme presunúť vyššie cenené prvky, zvyčajne na pravej strane, a nižšej hodnote prvky všeobecne doľava, ako by sme očakávali. Chceme, aby spodná veci boli v začiatok, a vyššie veci byť na konci. 

Ako to robíme? No v pseudokódu kódu, Dalo by sa povedať, poďme nastaviť počítadlo odkladacie nenulovú hodnotu. Uvidíme, prečo to robíme, že v sekunde. A potom sme zopakovať nasledujúce Proces, keď čítač swap je 0, alebo kým nerobíme swapy vôbec. 

Vynulujte počítadlo odkladacia 0, ak to nie je už 0. Potom sa pozrite na každý priľahlé dvojice prvkov. Ak sa tieto dva prvky sú nie je v poriadku, je vymeniť, a pridať 1 k pultu swapu. Ak uvažujete o to skôr, ako ho predstaviť, Všimnite si, že to bude pohybovať nižšia oceňujú prvky vľavo a vyššie oceňujú prvky vpravo, účinne robiť to, čo chceme robiť, čo je presunúť tieto skupiny prvkov týmto spôsobom. Poďme si predstaviť, ako to môže vyzerať pomocou našej ponuku že používa na testovanie out týchto algoritmov. Máme tu k netriedené poľa znova, označené všetky prvky je v červenej farbe. A obrátil som počítadlo odkladacia na nenulovú hodnotu. Aj ľubovoľne si vybral Negatívny 1-- to nie je 0. Chceme, aby tento proces opakovať do pultu odkladacieho 0. To je dôvod, prečo som nastaviť svoj swapu v rozpore s nejakou nenulovú hodnotu, pretože inak odkladací pult by byť 0. Nemali by sme ani začne plynúť Spôsob podľa tohto algoritmu. Takže znova, kroky are-- vynulovať počítadlo odkladacia na 0, potom sa pozrite na každom priľahlý pair, a či sú mimo prevádzky, je vymeniť, a pridať 1 k pultu swapu. Takže poďme začať tento proces. Takže prvá vec, ktorú robíme, je nastavíme čítač odkladacie na 0, a potom začneme hľadať v každej susednej dvojice. 

Tak sme najprv začať uvažovať o 5 a 2. Vidíme, že sú mimo objednať a tak sme ich vymeniť. A pridáme 1 k pultu swapu. Takže teraz náš čítač swap je 1, a 2 a 5 boli prepnutý. Teraz sme opäť proces opakovať. 

Pozerali sme sa na ďalšiu susedné dvojice, 5 a 1-- sú tiež mimo prevádzku, tak sme ich vymeniť a pridať 1 k pultu swapu. Potom sa pozrieme na 5 a 3. Sú mimo prevádzky, takže sme vymeniť je a pridáme 1 k pultu swapu. Potom sa pozrieme na 5 a 6. Sú v poriadku, takže my vlastne je potrebné vymeniť čokoľvek tentoraz. Potom sa pozrieme na 6 a 4. Sú tiež mimo prevádzky, takže sme vymeniť je a pridáme 1 k pultu swapu. 

Teraz si všimnúť, čo sa stalo. Presunuli sme 6 celú cestu až do konca. Takže vo výbere druhu, ak ste vidieť, že video, čo sme urobili, bolo sme skončili pohybom Najmenší prvky v budove roztriedený poľa v podstate od zľava doprava, najmenší k najväčšej. V prípade bublina druhu, keď sme po tejto konkrétnej algoritmus, my vlastne bude stavať roztriedený poľa sprava doľava, najväčší po najmenšie. Máme skutočne bublala 6, Najväčšia hodnota, až do konca. 

A tak teraz môžeme vyhlásiť, že je triedený, a v budúcnosti iterations-- prechádza pole again-- nemusíme uvažovať už 6. Máme len zvážiť netriedeného prvky keď sa pozeráme na susedných párov. Takže sme skončili jeden prejsť bublina druhu. Takže teraz sa vrátime k otázke, opakujte, kým počítadlo swap je 0. No counter swapu je 4, takže ideme aby znovu opakovať tento proces. 

Chystáme sa vynulovať počítadlo odkladací na 0, a pozrieť sa na každým susedným párom. Takže začneme s 2 a 1-- sú mimo prevádzky, takže sme ich vymeniť a pridáme 1 k pultu swapu. 2 a 3, sú v poriadku. Nepotrebujeme nič robiť. 3 a 5 sú v poriadku. Nepotrebujeme nič robiť tam. 

5 a 4, sú mimo prevádzku, a tak sme je potrebné ich vymeniť a pridať 1 k pultu swapu. A teraz sme sa presťahovali 5, Budúci najväčšie prvok, na koniec netriedeného časti. Takže môžeme teraz hovoriť, že časť usporiadané časti. 

Teraz pri pohľade na obrazovky a pravdepodobne môže povedať, ako môžem, aby polia Je radené práve teraz. Ale nemôžeme dokázať, že doteraz. Nemáme záruku že je to triediť. Ale to je miesto, kde swap Počítadlo to príde do hry. 

Preto sme dokončili a nahráva. Počítadlo swap je 2. Takže budeme opakovať sa tento proces, opakujte, kým počítadlo swap je 0. Vynulujte počítadlo odkladacie 0. Takže my ho resetovať. 

Teraz sa pozrite na každým susednom párom. To je v poriadku, 1 a 2. 2 a 3 sú v poriadku. 3 a 4 sú v poriadku. Takže v tomto bode, Všimnite si, že sme dokončili pri pohľadu na každej susednej dvojice, ale počítadlo swap je stále 0. 

Ak nebudeme musieť prejsť niektoré prvky, potom sa musí byť v poriadku tým, že Na základe tohto procesu. A tak účinnosťou druhov, Že sme počítačoví odborníci milujeme, je teraz môžeme vyhlásiť, celé pole musí triedené, pretože sme nemali musieť vymeniť akékoľvek prvky. To je celkom pekné. 

Takže to, čo je najhorší prípad Scenár s bublinkové radenia? V najhoršom prípade je pole v úplne opačnom poradí, a preto musíme bublina každý veľkých prvkov all cestu cez pole. A my efektívne musieť tiež bublina všetkých malých prvkov späť celú cestu cez pole, tiež. Takže každý z n elementy sa musí pohybovať v rámci všetkých ostatných n elementy. Tak to je ten najhorší možný scenár. V najlepšom prípade scenár aj keď, je to mierne líši od výberu druhu. Pole je už radené keď ideme dovnútra. My nemusíme vykonávať žiadne swapy na prvom prechode. Takže možno budeme musieť hľadať na menej prvkov, nie? My nemusíme opakovať spracovať niekoľkokrát viac než. 

Takže čo to znamená? Takže to, čo je najhorší možný scenár k Bubble druhu, a to, čo je najlepší scenár pre bubble druhu? Vedeli ste, že toto? V najhoršom prípade musíte iterovat naprieč všetkými n elementy n-krát. Takže najhorší prípad je n na druhú. 

V prípade, že pole je dokonale triedených aj keď, len vy sa pozrieť na seba prvkov raz. A v prípade, že počítadlo swap je stále 0, môžete povedať toto pole je triedený. A tak v najlepšom prípade sa jedná vlastne lepšie ako výber sort-- to je omega n. 

Som Doug Lloyd. To je CS50.