>> MARK GROZEN-SMITH: Hej, jeg er Mark Grozen-Smith, og det er QuickSort.
Ligesom indsættelse sortere og boble sortere QuickSort er en algoritme til
sortering en liste eller en matrix af ting.
For nemheds skyld lad os antage, at de ting er bare heltal, men
vide, at QuickSort arbejder for mere end blot tal.
Quickstart er en smule mere kompliceret end indsættelse eller boble, men det er
også langt mere effektiv i de fleste tilfælde.
Vent et sekund.
Sagde han "mest tilfælde ", ikke" alle "?
Interessant, no.
Ikke alle tilfælde er de samme.
Må ikke bekymre dig om denne detalje, hvis du har ikke set store O notation endnu, men
QuickSort er en O (n kvadreret) algoritme i værste fald, ligesom
indsættelse eller boble slags.
Men det fungerer typisk meget mere som en gammel analog m algoritme.
Hvorfor?
Det vender vi tilbage til senere.
Men for nu, lad os bare lære hvordan QuickSort fungerer.
>> Så lad os gå gennem Quicksorting dette vifte af heltal fra den mindste
til den største.
Her har vi de hele tal 6, 5, 1, 3, 8, 4, 7, 9 og 2.
Først, vi vælger det sidste element af dette array - i dette tilfælde to -
og kalder det en "pivot". Desuden, vi begynder at se på to ting -
ene, det laveste indeks, som jeg vil henvise som opholder sig til højre for
væggen, og, to, længst til venstre element, som jeg vil kalde "den nuværende
element. "Hvad vi kommer til at gøre, er se alle de andre elementer, andre
end pivot, og lægge alle de elementer mindre end drejetappen til
venstre væg og alle de større end pivot til
højre for væggen.
Så endelig, vil vi droppe pivot lige på den mur at sætte det mellem
alle tal er mindre end den og alle tal større.
>> Så lad os gøre det.
Saml de 2, sætte væggen i begyndelse, og kalder 6 "den nuværende
element. "Så vi ønsker at se på vores aktuelle element, 6.
Og da det er større end 2, vi overlade det der til
højre for væggen.
Derefter bevæger vi os videre til at se på de 5 som vores aktuelle element og se, at denne
er igen større end drejetappen, så vi forlade det, hvor det er på den højre
side af væggen.
Vi videre.
Vores nuværende element er nu 1, og - oh.
Det er anderledes nu.
Den aktuelle element er nu mindre end pivot, så vi ønsker at sætte det
til venstre for væggen.
For at gøre dette, lad os bare skifte aktuelle element med det laveste indeks
sidder lige til højre for væggen.
Nu bevæger vi muren op ene indeks så 1 er til venstre
side af væggen nu.
>> Vent.
Jeg bare blandet op elementerne på højre side af væggen, gjorde jeg ikke?
Må ikke bekymre dig.
Det er fint.
Det eneste, vi bekymrer os om for nu er, at alle disse elementer til
højre for væggen er større end pivot.
Forudsættes ingen faktiske orden endnu.
>> Nu tilbage til sortering.
Så vi fortsætter med at se på resten af ​​elementerne.
Og i dette tilfælde ser vi, at der er ingen andre elementer mindre end
pivot, så vi forlader dem alle på højre side af væggen.
Endelig får vi at det aktuelle element og se, at det er omdrejningspunktet.
Nu betyder det, at vi har to sektioner af matrixen, den første er
små på pivot og på venstre side af væggen, og den anden er
større end pivot til højre side af væggen.
Vi ønsker at sætte pivot element mellem de to, og så vil vi vide
at pivot er i sin ret endelig sorterede sted.
Så vi tænder det første element på højre side af væggen med pivot,
og vi kender pivot s i sin rigtige position.
>> Vi derefter gentage denne proces for den subarrays venstre og højre for pivot.
Siden sidste subarray er kun én element lang, vi ved, det er allerede
sorteret fordi hvordan kan du være ude af ordre, hvis du er kun et element?
På højre side af undergrupperingen vi se, at pivot er 5, og væggen
er lige til venstre for 6.
Og den nuværende element også starter ud som 6.
Så 6 er større end 5.
Vi overlader det, hvor det er på den højre side af væggen.
Nu bevæger sig på, 3 er mindre end 5..
Så vi skifter det med det første element lige til højre for væggen.
Nu flyttede jeg muren op én.
Nu går videre til 8..
8 er større end 5, og så vi forlader den.
De 4 er mindre end 5, så vi skifte det.
Og på.
>> Hver gang vi gentage processen på venstre og højre side af array. vi
vælge en pivot og gøre sammenligningerne og skabe et andet niveau af venstre og
rigtige subarrays.
Denne rekursivt kald vil fortsætte indtil vi når til slutningen, når vi har
opdeles den samlede array i bare subarrays af længde 1.
Derfra ved vi array sorteres fordi hvert element har på
et tidspunkt været en drejetap.
Med andre ord, for hvert element, alle tallene til venstre er mindre
værdier og alle de numre til højre har større værdier.
>> Denne fremgangsmåde fungerer godt, hvis værdien af ​​den valgte pivot er
omtrent i midten vifte af listeværdierne.
Dette ville betyde, at efter vi flytter elementer rundt, er der omtrent lige så mange
elementer til venstre for pivot , som der er til højre.
Og del-og-hersk karakter QuickSort algoritme tages derefter
fuld fordel af.
Dette skaber en runtime af O (n log n,) n, fordi vi har at gøre n minus 1
sammenligninger af hver generation og log n fordi vi er nødt til at opdele listen
log n gange.
Men i de værste tilfælde, dette algoritme kan faktisk være O (n
potens.) Antag på hver generation, omdrejningspunktet bare så sker for at være den
mindste eller den største af de numre vi sortering.
Dette ville betyde at bryde ned på listen n gange og Tage N minus 1
sammenligninger hver eneste gang.
Således o n potens.
>> Hvordan kan vi forbedre den metode?
En god måde at forbedre metoden er at skære ned på sandsynligheden for, at
runtime er nogensinde rent faktisk o n potens.
Husk dette værste worst case scenario kan kun ske, når
pivot valgt er altid den højeste eller laveste værdi i array.
For at sikre dette er mindre tilbøjelige til at ske, vi kan finde pivot
vælge flere elementer og tager medianen.
>> Mit navn er Mark Grozen-Smith, og dette er CS50.
>> For nemheds skyld lad os antage, at de ting er bare heltal, men
ved, at Quicksert -
Quicksert?
Undskyld.
>> Her har vi de hele tal 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Virkelig?
>> SPEAKER 2: Du må ikke stoppe der.
>> SPEAKER 1: Virkelig?