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