[Powered by Google Translate] [BUBBLE SORT] [JACKSON STEINKAMP Harvard University] [THIS IS CS50. CS50TV] Bubble Sort je príklad triedenie algoritmu - to znamená, že postup pre triedenie sadu prvkov v vzostupne alebo zostupne. Napríklad, ak ste chceli triediť pole skladajúci sa z čísel [3, 5, 2, 9], by správne vykonávanie Bubble Zoradiť vráti zoradené pole [2, 3, 5, 9] vo vzostupnom poradí. Teraz, budem vysvetľovať v pseudokódu, ako algoritmus funguje. Povedzme, že máme radenie zoznamu celých čísel 5 - 3, 2, 9, 6, a 5. Algoritmus začína pri pohľade na prvé dva prvky, 3 a 2, a kontrolovať, či sú mimo prevádzky vzhľadom k sebe. Sú - 3 je väčší ako 2. Ak chcete byť vo vzostupnom poradí, mali by byť iná cesta okolo. Takže, vymeníme ich. Teraz zoznam vyzerá nasledovne: [2, 3, 9, 6, 5]. Ďalej sa pozrieme na druhej a tretej prvkov, 3 a 9. Sú v správnom poradí vzhľadom k sebe navzájom. To znamená, že 3 je menší ako 9 tak, že algoritmus nie je vymeniť je. Ďalej sa pozrieme na 9 a 6. Sú mimo prevádzky. Takže, musíme vymeniť, pretože 9 je väčší ako 6. Konečne sa pozrieme na posledných dvoch celých čísel, 9 a 5. Sú mimo prevádzky, a preto musí byť vymenený. Po prvom kompletnom prechode zoznamu, vyzerá nasledovne: [2, 3, 6, 5, 9]. Nie je to zlé. Je to skoro zoradené. Ale musíme prejsť zoznam znova, aby si to úplne zoradené. Dva je menší ako 3, takže nie vymeniť je. Tri je menšie ako 6, takže nie vymeniť je. Šesť je väčší ako 5. My vymenili. Šesť je menšia ako 9. Nechceme vymeniť. Po druhom prechode, to vyzerá takto: [2, 3, 5, 6, 9]. Perfect. Teraz, poďme napísať, že v pseudokódu. V podstate, pre každý prvok v zozname, musíme sa na to pozrieť a prvok priamo k jeho pravej strane. Ak sú mimo prevádzky vo vzťahu k sebe - to znamená, že v prípade, že prvok vľavo je väčší ako na pravej strane - by sme mali vymeniť dva prvky. Robíme to pre každý prvok zoznamu, a urobili sme jeden priechod cez. Teraz len musíme robiť pass-through toľkokrát, aby zoznam je plne riadne zoradené. Ale koľkokrát musíme prejsť v zozname zaručiť, že sme urobili? No, najhorší scenár je, ak budeme mať úplne dozadu zoznam. Potom sa množstvo zložiť priechodiek, ktorá sa rovná počtu prvkov n-1. Ak to nedáva zmysel intuitívne, myslieť na jednoduchom prípade - zoznam [2, 1]. To bude trvať jeden pass-through triediť správne. [3, 2, 1] - V najhoršom prípade, že sa 3 prvky zoradené dozadu, to bude trvať 2 iterácií zoradiť. Po jednej iterácie, je to [2, 1, 3]. Druhý výnosy zoradené pole [1, 2, 3]. Takže viete, že nikdy nebudete musieť ísť cez pole, všeobecne, viac než n-1 krát, kde n je počet prvkov v poli. Je to tzv Bubble Sort, pretože najväčšie prvky majú tendenciu "bubble-up" doprava celkom rýchlo. V skutočnosti, tento algoritmus má veľmi zaujímavé správanie. Po m iteráciách cez celé pole, najviac vpravo m prvky sú zaručené ktoré majú byť triedené do ich správne miesto. Ak chcete vidieť to pre seba, môžeme vyskúšať na úplne dozadu zozname [9, 6, 5, 3, 2]. Po jednom prechode celého zoznamu, [Zvuk písania] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] úplne vpravo element 9 je na svojom mieste. Po druhom pass-through, bude mať 6 "bublala-up" na druhej nejpravější miesto. Tieto dva prvky na pravej strane - 6 a 9 - bude v ich správnych miestach po prvých dvoch Pass-priechodiek. Takže, ako môžeme použiť na optimalizáciu algoritmu? No, po jednej iterácie cez pole nemáme vlastne treba skontrolovať úplne vpravo prvok pretože vieme, že to sú zoradené. Po dvoch iteráciách, vieme určite najviac vpravo dva prvky sú na svojom mieste. Takže, všeobecne po kv iteráciách cez celú radom, Kontrola poslednej K prvkov je nadbytočná, pretože vieme, sú na správnom mieste už. Takže ak ste triedenie poľa n prvkov, na prvú iteráciu - budeš musieť roztriediť všetky prvky - prvý N-0. Na druhej iterácii, budete sa musieť pozrieť na všetky prvky, ale posledný - prvých n-1. Ďalšie optimalizácia môže byť zistiť, či je zoznam už je zoradený po každej iterácii. Ak je to už je zoradený, nepotrebujeme, aby sa žiadne ďalšie iterácie v zozname. Ako to môžeme urobiť? No, ak nebudeme robiť žiadne swapy na premietanie v zozname, je jasné, že zoznam bol už je zoradený, pretože sme nemali zameniť nič. Takže sme rozhodne nemusíme radiť znova. Možno by ste mohli inicializovať vlajky premennú s názvom "nie je zoradená" na false a zmeniť ho na hodnotu true, ak máte vymeniť akékoľvek prvky na jedna iterácia cez pole. Alebo podobne, aby sa počítadlo počítať, koľko swapy urobíte na danej iterácii. Na konci iterácie, ak nebola vymeniť niektorý z prvkov, viete, zoznam je už zoradená a máte hotovo. Bubble Sort, rovnako ako ostatné metódy radenia, môže byť vylepšený pracovať pre všetky prvky, ktoré majú usporiadanie metódy. To je vzhľadom k tomu, dva prvky máte spôsob, ako povedať, ak prvý je väčšia než, rovný alebo menší ako druhé. Napríklad by ste mohli radiť písmená abecedy vyslovením že a