MARK Grozen-SMITH: Ahoj, ja som Mark Grozen-Smith, a to je Quicksort. Rovnako ako vloženie druhu a bubliny triedenie, Quicksort je algoritmus pre triedenie zoznamu alebo poľa vecí. Pre jednoduchosť predpokladajme, že tí, veci sú len celé čísla, ale viem, že Quicksort pracuje pre viac než len čísla. Rýchly štart je trochu zložitejšie ako vloženie alebo bublina, ale je to tiež oveľa účinnejšie vo väčšine prípadov. Počkaj chvíľu. Povedal len povedať "najviac prípady, "nie" všetko "? Zaujímavé je, že nie. Nie všetky prípady sú rovnaké. Nebojte sa o tomto detaile, ak vám Nevidel veľký O notácie ešte, ale Quicksort je O (n štvorcový) algoritmus v najhoršom prípade, rovnako ako vloženie alebo bublina triedenie. Avšak, to zvyčajne pôsobí oveľa viac ako starý analógový m algoritmu. Prečo? Dostaneme sa k tomu vrátiť neskôr. Ale teraz, poďme sa len naučiť ako Quicksort funguje. 

Takže poďme prejsť Quicksorting to pole celých čísel od najmenšieho po najväčšie. Tu máme celé čísla 6, 5, 1, 3, 8, 4, 7, 9, a 2.. Po prvé, sme sa vybrať konečný prvok Toto pole - v tomto prípade dva - a volať, že je "pivot". Ďalej sme začať sa pozerať na dve veci - jeden, najnižší index, ktorý budem odkazovať ako zostať na pravej strane steny, a, dva, vľavo prvok, ktorý zavolám "prúd element. "Čo budeme robiť, je pozrite sa všetky ostatné prvky, ďalšie ako pivot, a dať všetky prvky menšie ako pivot na vľavo zo steny a všetky tie, väčšie ako pivot na priamo na stenu. Potom sa konečne budeme klesať pivot priamo na tej stene, aby ju medzi všetky čísla menšie, než a všetky čísla väčšie. 

Tak poďme na to. Zoberte 2, dať na stenu na začína, a zavolajte 6 "prúd element. "Takže chceme pozrieť na Naše aktuálne prvok, 6. A pretože je to väčšie ako 2, sme ju tam nechať, aby pravej steny. Potom sa presuňte na sa pozrieť na 5, pretože naše aktuálny prvok a uvidíte, že to je opäť väčšia, ako je čap, a tak sme nechajte ju tam, kde je na pravej strane bočné steny. Sme ďalej. Naše aktuálne prvok je teraz 1, a - oh. To je iná. Aktuálny prvok je teraz menšia než pivot, tak chceme, aby to na ľavej strane steny. Ak to chcete vykonať, poďme stačí prepnúť aktuálny prvok s najnižším indexom sedí len na pravej strane múru. Teraz sa presunieme na stenu jedného indexu tak 1 je na ľavej strane bočné steny súčasnosti. 

Počkajte. Len som poplietol prvky na na pravej strane múru, alebo nie? Nebojte sa. To je v poriadku. Jediné, čo nás zaujíma teraz je, že všetky tieto prvky do pravej steny sú väčšie než čapu. Žiadne skutočné poradí sa predpokladá ešte. 

Teraz späť k triedenia. Takže budeme pokračovať v pohľade na Zvyšok prvkov. A v tomto prípade vidíme, že existujú žiadne ďalšie prvky, menej ako pivot, takže sme sa nechať všetko na na pravej strane múru. Nakoniec sme sa dostať do aktuálneho prvku a uvidíte, že to je pivot. Teraz, to znamená, že máme dve časti poľa, prvý bytia malý na čapu a na ľavej strane múru, a na druhej bytosti väčšie ako pivot na na pravej strane múru. Chceme, aby otočný prvok medzi dva, a potom budeme vedieť, , Že čap je v jeho pravej konečné triedené miesto. Tak sme sa objavia prvé prvok na na pravej strane múru s čapom, a vieme, že čap je vo svojej správnej polohe. 

Tento postup sme potom opakujte pre subarrays vľavo a vpravo od čapu. Od posledného subarray je len jeden prvok dlho, vieme, že to už triedené, pretože ako môžete byť z objednať, ak ste len jeden prvok? Na pravej strane podsieť sme vidieť, že čap je 5, a The Wall je len vľavo od 6. A aktuálne prvok aj začína ako 6.. Takže 6 je väčšia ako 5 mm. Necháme ho tam, kde je na na pravej strane múru. Teraz, pohybujúce sa na, 3 je menej ako 5. Tak sme ju prepínať s prvým prvkom práve steny. Teraz som sa presťahoval na stenu do jedného. Teraz prejdeme k 8.. 8 je väčšia ako 5, a tak sme ju opustiť. 4 je menšia než 5, a tak sme ju prepínať. A na. A na. 

Zakaždým, keď sme sa zopakovať postup na ľavej a pravej strany poľa. my vybrať čap a vykonajte porovnanie a vytvoriť ďalšiu úroveň ľavého a pravej subarrays. Táto rekurzívne volanie bude pokračovať až do dôjdeme na koniec, keď sme rozdelil celkovej poľa do len subarrays o dĺžke 1. Odtiaľ vieme, že pole je radený preto, že každý prvok má, pri nejaký bod, bol pivot. Inými slovami, pre každý prvok, všetko čísla na ľavej strane sú menšie hodnoty a všetky čísla do právo mať väčšiu hodnotu. 

Táto metóda funguje veľmi dobre, ak hodnota zvolenej čapu je približne v strede Rozsah hodnôt zoznamu. To by znamenalo, že po tom, čo sme sa presunúť prvky okolo, tam asi toľko prvky na ľavej strane čapu ako tam sú vpravo. A rozdeľ a panuj povaha Quicksort algoritmus sa potom vyberie plná výhoda. Tým sa vytvorí runtime O (n log n) n, pretože musíme urobiť, n mínus 1 porovnanie na každú generáciu a log n preto, že musíme rozdeliť zoznam log n krát. Avšak, v najhoršom prípade, to Algoritmus sa môže v skutočnosti O (n druhú.) Predpokladajme, že v každej generácii, pivot len ​​tak sa stane, že je najmenší alebo najväčší čísla budeme triedenie. To by znamenalo, poškodí zoznam n krát a výroba n mínus 1 Porovnanie zakaždým. Tak, o n na druhú. 

Ako môžeme zlepšiť spôsob? Jeden dobrý spôsob, ako zlepšiť spôsob je znížiť na pravdepodobnosť, že runtime je niekedy skutočne o n na druhú. Nezabudnite tento najhorší, najhorší scenár môže dôjsť len, ak pivot zvolená vždy najvyššiu alebo najnižšie hodnoty v poli. Aby sa zabezpečilo, to je menej pravdepodobné, že sa tak stalo, nájdeme čap podľa výber viac prvkov a pričom medián. 

Moje meno je Mark Grozen-Smith, a to je CS50. 

Pre jednoduchosť predpokladajme, že tí, veci sú len celé čísla, ale vedieť, že Quicksert - Quicksert? Prepáčte. 

Tu máme celé čísla 6, 5, 1, 3, 8, 4, 9. 

SPEAKER 1: Naozaj? 

SPEAKER 2: Neprestávajte tu. 

SPEAKER 1: Naozaj?