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