>> 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.
>> 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?