>> MARK GROZEN-SMITH: Hei, olen Mark Grozen-Smith, ja tämä on Quicksort.
Aivan kuten lisäyslajittelu ja kupla lajitella, Quicksort on algoritmi
lajittelu lista tai joukko asioita.
Yksinkertaisuuden vuoksi oletetaan, että nämä asiat ovat vain kokonaislukuja, mutta
tietää, että Quicksort toimii enemmän kuin vain numeroita.
Quickstart on hieman monimutkaisempi kuin asettamisen tai kupla, mutta se on
myös paljon tehokkaampia useimmissa tapauksissa.
Hetkinen.
Sanoiko hän "kaikkein tapauksissa "ei" kaikki "?
Mielenkiintoista on, no.
Ei kaikissa tapauksissa ovat samat.
Älä ole huolissasi tämän yksityiskohdan jos ole nähnyt Big O merkintä vielä, mutta
Quicksort O (n potenssiin) algoritmi pahimmillaan, aivan kuten
paikoilleen tai kupla lajitella.
Kuitenkin, se toimii tyypillisesti paljon enemmän kuin vanha analoginen m algoritmi.
Miksi?
Palaamme siihen myöhemmin.
Mutta nyt haluan vain oppia miten Quicksort toimii.
>> Joten kulkea Quicksorting tämän joukko kokonaislukuja pienimmästä
suurimmalle.
Täällä meillä on kokonaislukuja 6, 5, 1, 3, 8, 4, 7, 9, ja 2.
Ensin haemme viimeisenä osana Tämän array - tässä tapauksessa kaksi -
ja soittaa, että "pivot." Seuraavaksi alkaa tarkastella kahta asiaa -
yksi, pienin indeksi, joka Kutsun niin pysyä oikealla
seinään, ja kaksi, vasemmanpuoleisin elementti, joka soitan "nykyinen
elementti. "Mitä me aiomme tehdä, on näyttää kaikki muut elementit, muut
kuin pivot, ja laittaa kaikki elementit pienempi kuin pivot
vasen seinä ja kaikki ne suurempi kuin pivot
oikea seinää.
Sitten lopuksi, me pudottaa pivot oikealle että seinälle laittaa se välillä
kaikki numerot pienempi kuin se ja kaikki numerot suurempi.
>> Tehdäänpä että.
Poimia 2, laittaa seinään alussa, ja soita 6 "nykyinen
elementti. "Joten haluamme tarkastella nykyinen elementti, 6.
Ja koska se on suurempi kuin 2, jätämme sen siihen
oikea seinää.
Sitten siirrymme katsomaan 5 meidän elementin ja nähdä, että tämä
on jälleen suurempi kuin pivot, joten jätä se jos se on oikealla
puolella seinää.
Siirrymme.
Nykyinen elementti on nyt 1, ja - oh.
Tämä on nyt erilainen.
Elementin on nyt pienempi kuin pivot, joten haluamme laittaa sen
vasemmalla puolella seinää.
Voit tehdä tämän, nyt vain vaihtaa elementin, jolla on pienin indeksi
istuu juuri oikealla seinään.
Nyt siirrymme seinää ylös yksi indeksi joten 1 on vasemmalla
puolella seinää nyt.
>> Odota.
Olen vain sekaisin elementtejä oikealla puolella seinää, enkö?
Älä huoli.
Se on hyvä.
Ainoa asia välitämme nyt on, että kaikki nämä tekijät
oikealla seinällä on isompi kuin pivot.
Mitään varsinaista järjestys oletetaan vielä.
>> Nyt takaisin lajittelu.
Joten jatkamme katsomalla loput elementit.
Ja tässä tapauksessa, näemme, että on olemassa no Muille aineille alle
pivot, joten jätämme ne kaikki oikealla puolella seinää.
Lopuksi saamme elementin ja nähdä, että se on pivot.
Nyt, se tarkoittaa, että meillä on kaksi osia array, joista ensimmäinen on
pieni akseli-ja vasemmalla puolella seinän, ja toinen on
suurempi kuin pivot oikealla puolella seinää.
Haluamme laittaa saranaelementin välillä kaksi, ja sitten me tiedämme
että nivel on sen oikeassa lopullinen lajitellut paikka.
Joten me vaihtaa ensimmäisen elementin oikealla puolella seinään pivot,
ja me tiedämme pivot n sen oikeaan asentoon.
>> Sitten toista tämä prosessi alaryhmien vasemmalla ja oikealla pivot.
Koska viimeinen alaryhmä on vain yksi elementti pitkä, me tiedämme, että on jo
lajitellut koska miten voit olla pois tilata jos olet vain yksi osa?
Sillä oikealla puolella alaryhmä, me nähdä, että nivel on 5, ja seinä
on vain jäljellä 6.
Ja elementin myös alkaa out 6.
Joten 6 on suurempi kuin 5.
Jätämme missä se on oikealla puolella seinää.
Nyt siirrymme, 3 on alle 5.
Joten me vaihtaa sen ensimmäisen elementin juuri oikealla seinään.
Nyt muutin seinään yhden.
Nyt siirrymme 8.
8 on suurempi kuin 5, ja niin jätämme sen.
4 on alle 5, joten kytke se.
Ja jatkuu.
>> Aina toistamme prosessin vasemmalla ja oikealla puolella jono. me
Valitse pivot ja tehdä vertailuja ja luoda toisen tason vasemmalle ja
oikea alaryhmien.
Tämä rekursiokutsu jatkuu lähestyessä loppuaan, kun olemme
jaetaan yleistä array osaksi vain alaryhmien pituuden 1.
Sieltä tiedämme array lajitellaan koska jokainen elementti on kello
Jossakin vaiheessa ollut pivot.
Toisin sanoen, jokainen elementti, kaikki numerot vasemmalle ovat vähemmän
arvot ja kaikki numerot oikeus on suuremmat arvot.
>> Tämä menetelmä toimii hyvin, jos arvo pivot valittu on
suunnilleen keskellä valikoima listan arvoja.
Tämä merkitsisi sitä, että sen jälkeen siirrymme elementtejä noin, siellä suunnilleen yhtä monta
elementtejä vasemmalla pivot koska on olemassa oikealle.
Ja hajota ja-valloittaa luonne Quicksort algoritmi otetaan sitten
täyden hyödyn.
Tämä luo runtime O (n log n,) n, koska meidän on tehtävä n miinus 1
vertailut jokainen sukupolvi ja log n, koska meillä on jakaa luettelon
log n kertaa.
Kuitenkin pahimmassa tapauksissa tämä algoritmi voi todella olla O (n
potenssiin.) Oletetaan kunkin sukupolven, pivot vain niin sattuu olemaan
pienin tai suurin numerot olemme lajittelu.
Tämä merkitsisi hajottaa lista n kertaa ja päätöksenteossa n miinus 1
vertailut joka ikinen kerta.
Siten O n potenssiin.
>> Miten voimme parantaa menetelmä?
Yksi hyvä tapa parantaa menetelmä on leikata todennäköisyys, että
runtime on koskaan itse O n potenssiin.
Muista tämä pahin pahimmassa tapauksessa voi tapahtua vasta, kun
pivot valittu on aina korkein tai pienimmän arvon jono.
Tämän varmistamiseksi on vähemmän todennäköisesti tapahtuu, voimme löytää Pivot
valitsemalla useita elementtejä ja ottaen mediaani.
>> Nimeni on Mark Grozen-Smith, ja tämä on CS50.
>> Yksinkertaisuuden vuoksi oletetaan, että nämä asiat ovat vain kokonaislukuja, mutta
tietää, että Quicksert -
Quicksert?
Anteeksi.
>> Täällä meillä on kokonaislukuja 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Todellako?
>> SPEAKER 2: Älä lopeta siellä.
>> SPEAKER 1: Todellako?