>> MARK GROZEN-SMITH: Hei, jeg er Mark Grozen-Smith, og dette er Quick.
Akkurat som innsetting sortere og boble sortere, er Quick en algoritme for
sortering en liste eller en rekke ting.
For enkelhets skyld, la oss anta at de ting er bare heltall, men
vet at Quick fungerer for mer enn bare tall.
Hurtigstart er en litt mer komplisert enn innsetting eller boble, men det er
også mye mer effektiv i de fleste tilfeller.
Vent et sekund.
Hadde han bare si "mest tilfeller ", ikke" alle "?
Interessant, nei.
Ikke alle tilfeller er de samme.
Ikke bekymre deg for dette detalj hvis du har ikke sett store O notasjon ennå, men
Quicksort er en O (n kvadrat) algoritme i verste fall, i likhet
innsetting eller boble slag.
Men vanligvis handler det mye mer som en gammel analog m algoritme.
Hvorfor?
Vi vil komme tilbake til det senere.
Men for nå, la oss bare lære hvordan Quick fungerer.
>> Så la oss gå gjennom Quicksorting dette matrise av heltall fra minste
til største.
Her har vi heltallene 6, 5, 1, 3, 8, 4, 7, 9 og to.
Først plukker vi den endelige element av Dette matrise - i dette tilfellet to -
og kaller det "pivot". Neste, vi begynne å se på to ting -
en, den laveste indeksen, som jeg vil referere til så bor til høyre
veggen, og to, med den venstre element, som jeg vil kalle den "nåværende
element. "Hva vi skal gjøre er se alle de andre elementene, andre
enn pivot, og sette alle elementene mindre enn dreie til
igjen av veggen og alle de større enn svinge til
høyre for veggen.
Så, til slutt, vil vi slippe pivot rett på veggen for å sette den mellom
alle tall som er mindre enn den og alle tallene større.
>> Så la oss gjøre det.
Plukk opp to, sette veggen på begynner, og kalle den 6 "gjeldende
element. "Så vi ønsker å se på vår nåværende element, den 6.
Og siden det er større enn 2, lar vi det derfra til
høyre for veggen.
Deretter flytter vi på å se på fem som vår aktuelle elementet og se at dette
er, igjen, er større enn svinge, så vi la den være der den er på høyre
side av veggen.
Vi gå videre.
Vår nåværende element er nå en, og - oh.
Dette er annerledes nå.
Den aktuelle elementet er nå mindre enn pivot, så vi ønsker å sette det
til venstre for veggen.
For å gjøre dette, la oss bare slå det aktuelle elementet med lavest indeks
sitter like til høyre for veggen.
Nå flytter vi veggen opp en indeks slik at en er på venstre
side av veggen nå.
>> Vent.
Jeg bare blandet opp elementene på høyre side av veggen, gjorde jeg ikke?
Ikke bekymre deg.
Det er fint.
Det eneste vi bryr oss om for nå er at alle disse elementer i
høyre for veggen er større enn pivot.
Ingen faktiske rekkefølgen er ennå antatt.
>> Nå, tilbake til sortering.
Så vi fortsetter å se på resten av elementene.
Og i dette tilfellet, ser vi at det er ingen andre elementer mindre enn
pivot, så vi la dem alle på den høyre side av veggen.
Til slutt, vi får til det aktuelle elementet og se at det er pivot.
Nå, det betyr at vi har to deler av rekken, den første var
lite på pivot og på venstre side av veggen, og den andre er
større enn svinge til høyre side av veggen.
Vi ønsker å sette svingelement mellom de to, og så får vi vite
at dreie er i sin høyre endelig sortert sted.
Så slå det første element på høyre side av veggen med dreie,
og vi vet pivot sin i riktig posisjon.
>> Vi gjentar deretter denne prosessen for undergrupper venstre og høyre for pivot.
Siden den siste subarray er bare én element lang, vet vi at det allerede
sorterte fordi hvordan kan du være ute av bestille hvis du er bare ett element?
For høyre side av subarray, vi se at sving er 5, og veggen
er nettopp forlatt av seks.
Og det aktuelle elementet også starter ut som seks.
Så 6 er større enn fem.
Vi la den der den er på høyre side av veggen.
Nå, flytte på, 3 er mindre enn fem.
Så bytter vi det med det første elementet bare rett på veggen.
Nå, jeg flyttet veggen opp ett.
Nå går videre til åtte.
8 er større enn 5, og så vi lar det.
Den 4 er mindre enn 5, så vi slår det.
Og på.
>> Hver gang vi gjenta prosessen på venstre og høyre side av tabellen. vi
velge en pivot og gjøre sammenligninger og skape et annet nivå av venstre og
riktige undergrupper.
Denne rekursive kall vil fortsette til vi kommer til slutten når vi har
deles opp den samlede matrisen i bare undergrupper av lengde 1.
Derfra vet vi matrisen er sortert fordi hvert element har, på
enkelte punkt, vært en pivot.
Med andre ord, for hvert element, alt Tallene til venstre er mindre
verdier og alle numrene til retten har større verdier.
>> Denne metoden fungerer veldig bra hvis Verdien av den valgte svinge er
omtrent midt utvalg av liste verdier.
Dette ville bety at, etter at vi flytter elementer rundt, er det omtrent like mange
elementer til venstre for svinge som det er til høyre.
Og splitt-og hersk natur Quick algoritmen blir deretter tatt
full nytte av.
Dette skaper en gangtid på O (n log n,) n fordi vi har å gjøre n minus 1
sammenligninger på hver generasjon og log n fordi vi må dele opp listen
log n ganger.
Men, i de verste tilfellene, dette Algoritmen kan faktisk være O (n
squared.) Anta på hver generasjon, pivot bare så skjer for å være den
minste eller den største av tallene vi sortering.
Dette ville bety bryte ned på listen n ganger og Lage N minus 1
sammenligninger hver eneste gang.
Dermed o n squared.
>> Hvordan kan vi forbedre metoden?
En god måte å forbedre metoden er å kutte ned på sannsynligheten for at
runtime er noen gang faktisk o n squared.
Husk dette verste, worst case scenario kan bare skje når
svingtapp som velges, er alltid det høyeste eller laveste verdi i matrisen.
For å sikre dette er mindre sannsynlig til å skje, vi kan finne pivot ved
velge flere elementer og tar medianverdien.
>> Mitt navn er Mark Grozen-Smith, og dette er CS50.
>> For enkelhets skyld, la oss anta at de ting er bare heltall, men
vet at Quicksert -
Quicksert?
Unnskyld.
>> Her har vi heltallene 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Really?
>> SPEAKER 2: Ikke stopp der.
>> SPEAKER 1: Really?