MARK Grozen-SMITH: Ahoj, já jsem Mark Grozen-Smith, a to je Quicksort. Stejně jako vložení druhu a bubliny třídění, Quicksort je algoritmus pro třídění seznamu nebo pole věcí. Pro jednoduchost předpokládejme, že ti, věci jsou jen celá čísla, ale vím, že Quicksort pracuje pro více než jen čísla. Rychlý start je trochu složitější než vložení nebo bublina, ale je to také mnohem účinnější ve většině případů. Počkej chvíli. Řekl jen říct "nejvíce případy, "ne" všechno "? Zajímavé je, že ne. Ne všechny případy jsou stejné. Nebojte se o tomto detailu, pokud vám Neviděl velký O notace ještě, ale Quicksort je O (n čtvercový) algoritmus v nejhorším případě, stejně jako vložení nebo bublina třídění. Nicméně, to obvykle působí mnohem více jako starý analogový m algoritmu. Proč? Dostaneme se k tomu vrátit později. Ale teď, pojďme se jen naučit jak Quicksort funguje. 

Takže pojďme projít Quicksorting to pole celých čísel od nejmenšího po největší. Zde máme celá čísla 6, 5, 1, 3, 8, 4, 7, 9, a 2.. Za prvé, jsme se vybrat konečný prvek Toto pole - v tomto případě dva - a volat, že je "pivot". Dále jsme začít se dívat na dvě věci - jeden, nejnižší index, který budu odkazovat jako zůstat na pravé straně stěny, a, dva, vlevo prvek, který zavolám "proud element. "Co budeme dělat, je podívejte se všechny ostatní prvky, další než pivot, a dát všechny prvky menší než pivot na vlevo ze zdi a všechny ty, větší než pivot na pravé stěny. Pak se konečně budeme klesat pivot přímo na té zdi, aby ji mezi všechna čísla menší, než a všechna čísla větší. 

Tak pojďme na to. Seberte 2, umístit na stěnu v začíná, a zavolejte 6 "proud element. "Takže chceme podívat na Naše aktuální prvek, 6. A protože je to větší než 2, jsme ji tam nechat, aby pravé stěny. Pak se přesuňte na se podívat na 5, protože naše aktuální prvek a uvidíte, že to je opět větší, než je čep, a tak jsme nechte ji tam, kde je na pravé straně boční stěny. Jsme dál. Naše aktuální prvek je nyní 1, a - oh. To je jiná. Aktuální prvek je nyní menší než pivot, tak chceme, aby to na levé straně stěny. Chcete-li to provést, pojďme stačí přepnout aktuální prvek s nejnižším indexem sedí jen na pravé straně zdi. Nyní se přesuneme na zeď do jednoho indexu tak 1 je na levé straně boční stěny nyní. 

Počkejte. Jen jsem popletl prvky na na pravé straně zdi, nebo ne? Nebojte se. To je v pořádku. Jediné, co nás zajímá teď je, že všechny tyto prvky do pravé stěny jsou větší než čepu. Žádné skutečné pořadí se předpokládá ještě. 

Nyní zpět k třídění. Takže budeme pokračovat v pohledu na Zbytek prvků. A v tomto případě vidíme, že existují žádné další prvky, méně než pivot, takže jsme se nechat všechno na na pravé straně zdi. Nakonec jsme se dostat do aktuálního prvku a uvidíte, že to je pivot. Nyní, to znamená, že máme dvě části pole, první bytí malý na čepu a na levé straně zdi, a na druhé bytosti větší než pivot na na pravé straně zdi. Chceme, aby otočný prvek mezi dva, a pak budeme vědět, , že čep je v jeho pravé konečné tříděné místo. Tak jsme se objeví první prvek na na pravé straně zdi s čepem, a víme, že čep je ve své správné poloze. 

Tento postup jsme pak opakujte pro subarrays vlevo a vpravo od čepu. Od posledního subarray je pouze jeden prvek dlouho, víme, že je již tříděné, protože jak můžete být z objednat, pokud jste jen jeden prvek? Na pravé straně podsoustavu jsme vidět, že čep je 5, a The Wall je právě odešel z 6.. A aktuální prvek i začíná jako 6.. Takže 6 je větší než 5 mm. Necháme ho tam, kde je na na pravé straně zdi. Nyní, pohybující se na, 3 je méně než 5. Tak jsme ji přepínat s prvním prvkem právě stěny. Teď jsem se přestěhoval na zeď do jednoho. Nyní přejdeme k 8.. 8 je větší než 5, a tak jsme ji opustit. 4 je menší než 5, a tak jsme ji přepínat. A na. A na. 

Pokaždé, když jsme se zopakovat postup na levé a pravé strany pole. my vybrat čep a proveďte srovnání a vytvořit další úroveň levého a pravé subarrays. Tato rekurzivní volání bude pokračovat až do dojdeme na konec, když jsme rozdělil celkové pole do jen subarrays o délce 1. Odtamtud, víme, že pole je uvedena proto, že každý prvek má, při nějaký bod, byl pivot. Jinými slovy, pro každý prvek, vše čísla na levé straně jsou menší hodnoty a všechna čísla do právo mít větší hodnotu. 

Tato metoda funguje velmi dobře, pokud hodnota zvolené čepu je přibližně ve středu Rozsah hodnot seznamu. To by znamenalo, že poté, co jsme se přesunout prvky kolem, tam asi tolik prvky na levé straně čepu jak tam jsou vpravo. A rozděl a panuj povaha Quicksort Algoritmus je pak vzat plně využívat. Tím se vytvoří runtime O (n log n,) n, protože musíme udělat, n minus 1 srovnání na každou generaci a log n proto, že musíme rozdělit seznam log n krát. Nicméně, v nejhorším případě, to Algoritmus může být ve skutečnosti O (n druhou.) Předpokládejme, že v každé generaci, pivot jen tak se stane, že je nejmenší nebo největší čísla budeme třídění. To by znamenalo, poškodí seznam n krát a výroba n mínus 1 Srovnání pokaždé. Tak, o n na druhou. 

Jak můžeme zlepšit způsob? Jeden dobrý způsob, jak zlepšit způsob je snížit na pravděpodobnost, že runtime je někdy skutečně o n na druhou. Nezapomeňte tento nejhorší, nejhorší scénář může dojít pouze, pokud pivot zvolena vždy nejvyšší nebo nejnižší hodnoty v poli. Aby se zajistilo, to je méně pravděpodobné, že se tak stalo, najdeme čep podle výběr několika prvků a přičemž medián. 

Mé jméno je Mark Grozen-Smith, a to je CS50. 

Pro jednoduchost předpokládejme, že ti, věci jsou jen celá čísla, ale vědět, že Quicksert - Quicksert? Promiňte. 

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

SPEAKER 1: Opravdu? 

SPEAKER 2: Nepřestávejte zde. 

SPEAKER 1: Opravdu?