>> MARK GROZEN-SMITH: Hej, jag är Mark Grozen-Smith, och detta är Quick.
Precis som inför sortera och bubbla sortera, är Quick en algoritm för
sortera en lista eller en mängd saker.
För enkelhetens skull låt oss anta att de saker är bara heltal, men
vet att Quick fungerar för mer än bara siffror.
Snabbstart är lite mer komplicerad än insättning eller bubbla, men det är
också mycket mer effektiv i de flesta fall.
Vänta en sekund.
Sa han bara säga "de flesta fall ", inte" alla "?
Interestingly, nr.
Inte alla fall är desamma.
Oroa dig inte för denna detalj om du har inte sett big O nota ännu, utan
Quick är en O (n kvadrat) algoritm i värsta fall, precis som
insättning eller bubbla slag.
Dock fungerar den normalt mycket mer som en gammal analog m algoritm.
Varför?
Vi återkommer till det senare.
Men för nu, låt oss bara veta hur Quick fungerar.
>> Så låt oss gå igenom Quicksorting detta matris med heltal från minsta
till största.
Här har vi heltalen 6, 5, 1, 3, 8, 4, 7, 9, och 2.
Först, vi plockar den sista delen av denna samling - i det här fallet, två -
och kalla det för "pivot". Nästa, vi börjar titta på två saker -
ett, den lägsta index, som jag ska hänvisa till som vistas till höger om
väggen, och, två, längst till vänster element, som jag kallar det "nuvarande
element. "Vad vi ska göra är att ser alla andra element, andra
över sväng, och lägga alla element mindre än sväng till
kvar av väggen och alla de större än det vrid till
höger av väggen.
Då, äntligen, vi släpper sväng höger på väggen för att sätta den mellan
alla tal som är mindre än det och alla nummer större.
>> Så låt oss göra det.
Plocka upp 2, sätta på väggen på början, och kallar den 6 den "nuvarande
element. "Så vi vill titta på vår nuvarande elementet, den 6.
Eftersom det är större än det 2, vi lämnar det där till
höger av väggen.
Sedan går vi vidare för att titta på de 5 som vår aktuellt element och se till att detta
är återigen större än det vrid, så vi lämna den där den är till höger
sida av väggen.
Vi går vidare.
Vår aktuella elementet är nu 1, och - oh.
Det är annorlunda nu.
Den aktuella elementet nu är mindre än pivot, så vi vill ha den
till vänster om väggen.
För att göra detta, låt oss bara växla aktuella elementet med lägst index
sitter precis till höger om väggen.
Nu flyttar vi muren upp ett index så att 1 är till vänster
sidan av väggen nu.
>> Vänta.
Jag blandade bara upp elementen på höger sida av väggen, inte jag?
Oroa dig inte.
Det är bra.
Det enda vi bryr oss om just nu är att alla dessa element till
höger av väggen är större än pivot.
Inga faktiska order antas ännu.
>> Nu, tillbaka till sortering.
Så vi fortsätter att titta på resten av elementen.
Och i det här fallet ser vi att det finns inga andra delar är mindre än den
pivot, så vi lämnar dem alla på höger sida av väggen.
Slutligen får vi till det aktuella elementet , och ser att det är sväng.
Nu innebär det att vi har två sektioner av matrisen, den första är
små på tappen och på den vänstra sidan av väggen, och den andra är
större än det vrid till högra sidan av väggen.
Vi vill sätta svängelementet mellan de två, och sedan kommer vi att veta
att sväng är i sin rätt final sorterad plats.
Så vi byter det första elementet på höger sida av väggen med den pivot,
och vi vet sväng s i rätt läge.
>> Vi upprepa sedan denna process för subsystemen vänster och höger om pivot.
Sedan den senaste subsystemet är bara en element långt, vi vet att det redan
sorterad eftersom hur kan du vara ur beställa om du är bara en del?
För den högra sidan av subarray, vi se att sväng är 5, och väggen
har just lämnat av 6.
Och det aktuella elementet också börjar som den 6.
Så 6 är större än 5.
Vi lämnar det där det är på högra sidan av väggen.
Nu går vi vidare, är 3 mindre än 5.
Så vi slå med det första elementet lagom av väggen.
Nu, jag flyttade väggen upp ett.
Nu går vi vidare till 8.
8 är större än 5, och så vi lämnar det.
Den 4 är mindre än 5, så vi slå.
Och den.
>> Varje gång vi upprepa processen på vänstra och högra sidorna av matrisen. vi
välja en pivot och göra jämförelser och skapa en annan nivå på vänster och
rät subsystem.
Denna rekursivt anrop kommer att fortsätta tills vi når slutet, när vi har
delat upp den totala utbud i bara subsystem av längd 1.
Därifrån, vi vet arrayen sorteras eftersom varje element uppvisar, vid
någon gång, haft en pivot.
Med andra ord, för varje element, allt siffrorna till vänster är mindre
värden och alla nummer till höger har större värden.
>> Denna metod fungerar mycket bra om det värde av sväng valts är
ungefär i mitten intervallet av listvärden.
Detta skulle innebära att, när vi går element runt, där ungefär lika många
element till vänster om svängtappen eftersom det finns till höger.
Och söndra och erövring karaktär Quick algoritm tas sedan
full nytta av.
Detta skapar en runtime av O (n log n,) n eftersom vi har att göra n minus 1
jämförelser på varje generation och log n eftersom vi måste dela upp listan
log n gånger.
Men i värsta fall, detta Algoritmen kan faktiskt vara O (N
kvadrat.) Antag på varje generation, sväng bara så händer att vara den
minsta eller den största av de siffror vi sortering.
Detta skulle innebära att bryta ner i listan n gånger och gör n minus 1
jämförelser varje gång.
Således o n i kvadrat.
>> Hur kan vi förbättra metoden?
Ett bra sätt att förbättra metoden är att skära ner på sannolikheten att
runtime är någonsin faktiskt o n i kvadrat.
Tänk på det värsta, värsta scenario kan bara hända när
pivot valts är alltid den högsta eller lägsta värdet i uppsättningen.
För att säkerställa detta är det mindre troligt att hända, vi kan hitta sväng genom
välja flera element och med medianvärdet.
>> Mitt namn är Mark Grozen-Smith, och detta är CS50.
>> För enkelhetens skull, låt oss anta att de saker är bara heltal, men
vet att Quicksert -
Quicksert?
Ursäkta.
>> Här har vi heltalen 6, 5, 1, 3, 8, 4, 9.
>> HÖGTALARE 1: Verkligen?
>> HÖGTALARE 2: Sluta inte där.
>> HÖGTALARE 1: Verkligen?