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