MARK Grozen-Smith: Tere, ma olen Mark Grozen-Smith ja see on Quicksort. Just nagu sisestamise sort ja mull sort, Quicksort on algoritm sorteerimine nimekirja või array asju. Lihtsuse mõttes eeldame, et need asjad on täisarvud, kuid tean, et Quicksort töötab enamat kui lihtsalt numbreid. Kiirstart on natuke keerulisem kui sisestamist või mull, kuid see on Samuti palju tõhusam enamikel juhtudel. Oota. Kas ta just "kõige juhtudel "ei" kõik "? Huvitaval kombel ei. Mitte kõigil juhtudel on sama. Ära muretse see detail, kui te ei ole näinud suur O märke, aga Quicksort on O (n ruudus) algoritm halvimal juhul, nagu ka sisestamist või mull sort. Siiski tavaliselt tegutseb palju nagu vana analoog m algoritm. Miks? Me saame hiljem tagasi. Aga nüüd, lihtsalt õppida kuidas Quicksort toimib. 

Nii Vaatame Quicksorting see massiivi täisarvud väikseim et suurim. Siin on täisarvud 6, 5, 1, 3, 8, 4, 7, 9 ja 2. Kõigepealt vali viimane element Selle massiivi - antud juhul kaks - ja helistada, et "pivot". Edasi me hakata vaatama kahte asja - üks, mis on madalaim indeks, mis ma viidata kui jäädes õigus seina ja kahe vasakpoolsema element, mida ma kutsun "praegune element. "Mis me teeme, on vaata kõiki muid elemente, muu kui pivot, ja panna kõik elemendid väiksem pöördtapi vasakule seina ja kõik need suurem pöördtapi õigus seina. Siis lõpuks, me tilk pivot otse selle seina panna see vahel kõik numbrid väiksem, kui see ja kõik numbrid suuremad. 

Teeme seda. Korja 2, pange seina algab ja helistage 6 "praegune element. "Nii et me tahame vaadata meie praegune element, 6. Ja kuna see on suurem kui 2, jätame selle seal õigus seina. Siis liigume edasi ja vaatame, 5 nagu meie praegune element ja näen, et see on jällegi suurem šarniir, seega jätta, kui see on õige pool seina. Me liigume edasi. Meie praegune element on nüüd 1, ja - oh. See on nüüd muutunud. Praegune element on nüüd väiksem pivot, nii et me tahame panna vasakul seina. Selleks, lihtsalt lülitage praegune element madalaima indeks istub lihtsalt paremal seina. Nüüd astume seina üles üks indeks nii 1 on vasakul pool seina nüüd. 

Oota. Ma lihtsalt sassi elemendid paremal pool seina, eks? Ära muretse. See on hea. Ainuke asi, me hoolime nüüd on, et kõik need elemendid paremal seinal on suurem kui pivot. Tegelikku et eeldatakse veel. 

Nüüd tagasi sorteeritakse. Nii me jätkata vaadates ülejäänud elemendid. Ja sel juhul näeme, et seal on mingit muud elemendid alla pivot, et jätame nad kõik paremal pool seina. Lõpuks saame praeguse element ja näen, et see on teljeks. Nüüd tähendab see, et meil on kaks lõigud massiivi, millest esimene on väikeste kohta šarniir ja vasak pool ning seina ja teine ​​on suurem pöördtapi paremal pool seina. Tahame panna pöördeelementi vahel kaks, ja siis me teame, et pivot on tema õige lõplik sorteeritud koht. Nii me lülitage esimene element on paremal pool seina pivot, ja me teame, pivot on oma õigesse asendisse. 

Me korrake seda protsessi subarrays vasakul ja paremal teljeks. Kuna viimane subarray on ainult üks element pikk, me teame, et see on juba sorteeritud, sest kuidas sa saad olla välja tellida kui sa oled ainult üks element? Paremal küljel subarray oleme näha, et pivot on 5 ja seina on lihtsalt jäänud 6. Ja praegune element ka hakkab läbi 6. Niisiis 6 on suurem kui 5 mm. Jätame selle, kus ta on paremal pool seina. Lähme nüüd edasi, 3 on väiksem kui 5. Nii me lülitage see esimese elemendi just seina. Nüüd kolisin seina üles üks. Lähme nüüd edasi kuni 8. 8 on suurem kui 5, ja nii me jätame selle. 4 on väiksem kui 5, nii et me lülita. Ja edasi. Ja edasi. 

Iga kord, kui me protsessi korrata vasakul ja paremal pool massiiv. me vali pivot ja teha võrdlusi ja luua uus tase vasakule ja õige subarrays. See rekursiivne kõne jätkub jõuame lõpuks, kui me oleme jagatud kogu massiiv lihtsalt subarrays pikkusega 1. Sealt me ​​teame massiiv sorteeritud sest iga element on, at Mingil hetkel on pivot. Teisisõnu, iga element on kõigil Numbrite vasakul on vähemal väärtused ja kõik numbrid õigus on suuremad väärtused. 

See meetod toimib väga hästi, kui väärtus teljeks valitud on umbes keskel vahemikus nimekiri väärtused. See tähendaks, et pärast me liigume elementide ümber, umbes nii palju elemendid vasakus šarniir kui on paremale. Ja jaga ja vallutada, milline on Quicksort algoritmi siis võetakse täielikult ära. See loob runtime O (n log n) n, sest me peame tegema n miinus 1 võrdlused iga põlvkond ja log n, sest meil on jagada nimekiri log n korda. Kuid halvimal juhul on see Algoritm võib tegelikult olla O (n ruudus.) Oletame, iga põlvkond, pivot lihtsalt nii juhtub olema väikseim või suurim numbrid pakin. See tähendaks, lõhkudes nimekiri n korda ja tegemine n miinus 1 võrdlusi iga kord. Seega o n ruudus. 

Kuidas me saame seda meetodit parandada? Üks hea võimalus parandada meetod vähendama tõenäosust, et Pikkus on kunagi tegelikult o n ruudus. Pea meeles, see halvim, kõige mustema stsenaariumi saab toimuda ainult siis, kui pivot valitud on alati kõrgeim või väikseima väärtuse massiivi. Selle tagamiseks on vähem tõenäoline, leiame pivot poolt Valides mitu elementi ja võttes mediaan. 

Minu nimi on Mark Grozen-Smith, ja see on CS50. 

Lihtsuse mõttes eeldame, et need asjad on täisarvud, kuid tean, et Quicksert - Quicksert? Vabandust. 

Siin on täisarvud 6, 5, 1, 3, 8, 4, 9. 

SPEAKER 1: Tõesti? 

SPEAKER 2: Ärge peatuda. 

SPEAKER 1: Tõesti?