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