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