[Powered by Google Translate] Tommy: Låt oss ta en titt på val Sortera, en algoritm
för att ta en lista med tal och sortera dem.
En algoritm, kom ihåg, är helt enkelt ett steg-för-steg
förfarande för att åstadkomma en uppgift.
Den grundläggande idén bakom val Sortera är att dela
vår lista i två delar -
en sorterad del och en osorterad parti.
Vid varje steg i algoritmen, är ett nummer flyttas från
osorterat parti till den sorterade delen tills slutligen
Hela listan är sorterad.
Så här är en lista över sex nummer -
23, 42, 4, 16, 8, och 15.
Just nu hela listan anses osorterat.
Även om ett antal som 16 kanske redan i sitt rätta
plats, har vår algoritm inte kan veta att tills
Hela listan är sorterad.
Så vi ska överväga varje nummer som ska osorterade tills vi sorterar
det själva.
Vi vet att vi vill att listan ska vara i stigande ordning.
Så vi kommer att vilja bygga upp den sorterade delen av vår lista
från vänster till höger, minsta till det största.
För att göra det, vi måste hitta den minsta osorterade elementet
och lägga den i slutet av den sorterade delen.
Eftersom denna lista inte är sorterad, är det enda sättet att göra det på
titta på varje element i osorterade delen, minns
vilket element är den lägsta och jämföra
varje element till det.
Så vi ska först titta på 23.
Detta är det första elementet som vi har sett, så vi kommer ihåg
det som ett minimum.
Nästa vi titta på 42.
42 är större än 23, så 23 är fortfarande ett minimum.
Nästa är 4 som är mindre än 23, så vi kommer ihåg 4
som det nya minimivärdet.
Nästa är 16 som är större än 4, så 4
är fortfarande ett minimum.
8 är större än 4, och 15 är större än 4, så 4 måste vara
det minsta elementet osorterat.
Så även om som människor kan vi genast se att 4 är
minsta elementet, måste vår algoritm för att titta på
Varje osorterade element även efter att vi har hittat 4 -
minsta elementet.
Så nu när vi har hittat den minsta delen, 4, vi vill
att flytta den till den sorterade delen av listan.
Eftersom detta är det första steget innebär detta att vi vill sätta 4 på
början av listan.
Just nu 23 är i början av listan, så
låt oss byta 4 och 23.
Så nu vår lista ser ut så här.
Vi vet att 4 skall vara i sitt slutliga läge, eftersom det är
både det minsta elementet och elementet i början
i listan.
Så detta betyder att vi inte skulle behöva flytta igen.
Så låt oss upprepa denna process för att lägga till ytterligare element till
sorterade delen av listan.
Vi vet att vi inte behöver titta på 4, eftersom det är
redan sorterade.
Så vi kan börja på 42, ​​vilket vi kommer ihåg som
minsta elementet.
Så nästa ska vi titta på den 23 som är mindre än 42, så vi
minns 23 är den nya miniminivån.
Nästa vi ser 16 som är mindre än 23, så
16 är det nya minimum.
Nu får vi titta på 8 som är mindre än 16, så
8 är den nya minsta.
Och slutligen 8 är mindre än 15, så vi vet att 8 är ett minimum
osorterat elementet.
Så det innebär att vi bör lägga 8 till den sorterade
delen av listan.
Just nu 4 är den enda sorterade elementet, så vi vill placera
den 8 bredvid 4.
Sedan 42 är det första elementet i den osorterade delen av
listan, vi vill byta 42 och 8.
Så nu vår lista ser ut så här.
4 och 8 representerar den sorterade delen av listan, och den
resterade siffrorna representerar osorterade
delen av listan.
Så låt oss fortsätta med en annan iteration.
Vi börjar med 23 den här gången, eftersom vi inte behöver titta på
den 4 och 8 längre eftersom de har
redan sorterats.
16 är mindre än 23, så vi kommer ihåg
16 som det nya minimivärdet.
16 är mindre än 42, men 15 är mindre än 16, så 15 måste vara
minsta osorterat elementet.
Så nu vill vi byta 15 och 23 till
ge oss den här listan.
Den sorterade delen av listan består av 4, 8 och 15, samt
dessa element är fortfarande osorterade.
Men det råkar vara så att nästa osorterade element, 16,
är redan sorterade.
Men det finns inget sätt för vår algoritm för att veta att 16
är redan i sin rätta plats, så vi måste fortfarande
upprepa exakt samma process.
Så vi ser att 16 är mindre än 42, och 16 är mindre än 23, så
16 måste vara det minsta elementet.
Det är omöjligt att byta denna del med sig själv, så att vi kan
bara lämna det på den här platsen.
Så vi behöver en mer pass av vår algoritm.
42 är större än 23, så 23 måste vara
minsta osorterade elementet.
När vi byta 23 och 42, vi sluta med vår sista
sorterad lista -
4, 8, 15, 16, 23, 42.
Vi vet 42 måste vara på rätt plats eftersom det är den
enda elementet kvar, och det är val Sortera.
Låt oss formalisera nu vår algoritm med några
pseudokod.
På rad ett, kan vi se att vi behöver integrera över
varje element i listan.
Utom det sista elementet, eftersom 1 element
Listan är redan sorterad.
På rad två, anser vi det första elementet i osorterade
del av listan är det minsta, som vi gjorde med vår
exempel, så vi har något att jämföra med.
Linje tre börjar en andra slinga där vi iterera över
varje osorterade element.
Vi vet att när jag iterationer, den sorterade delen
på vår lista måste jag element i det eftersom varje steg
sorterar ett element.
Så det första osorterade elementet måste vara i läge I plus 1.
På rad fyra, jämför vi det aktuella elementet till ett minimum
element som vi har sett hittills.
Om det aktuella elementet är mindre än den minsta
inslag, då vi minns det aktuella elementet som ny
minimum på linje fem.
Slutligen, på rad sex och sju, byta vi det minsta
element med det första osorterade elementet, vilket
lägga till det i den sorterade delen av listan.
När vi har en algoritm, en viktig fråga ställa
oss som programmerare är hur lång tid tog det att ta?
Vi kommer först fråga frågan hur lång tid tar det för
algoritm för att köra i värsta fall?
Minns vi representerar denna gång
tid med Big O notation.
För att bestämma den minsta osorterade elementet, vi
huvudsak hade att jämföra varje element i listan för att
varannan element i listan.
Intuitivt, detta låter som en O n kvadrat drift.
Titta på vår pseudokod, har vi också en slinga kapslat
annan slinga, som verkligen låter som en O
n kvadrat drift.
Kom dock ihåg att vi inte behövde se över
Hela listan vid fastställandet av minsta osorterade element?
När vi visste att 4 var sorterade, till exempel, gjorde vi inte
behöver titta på det igen.
Det gör det lägre gångtid?
För vår lista över längden 6, behövde vi göra fem
jämförelser för det första elementet, fyra jämförelser för
det andra elementet, och så vidare.
Det innebär att det totala antalet steg är summan av
heltalen från 1 till längden av listan minus 1.
Vi kan representera detta med en summering.
Vi kommer inte att gå in summeringar här.
Men det visar sig att denna summering är lika med n gånger
n minus 1 över 2.
Eller ekvivalent n kvadrerade över 2 minus n över 2.
När man talar om asymptotisk runtime, detta N kvadrerade termen
kommer att dominera denna N sikt.
Så val typ är O n kvadrat.
Minns att i vårt exempel, val Sortera fortfarande behövde
kontrollera om ett nummer som redan sorterades
behövde flyttas.
Så det betyder att om vi körde val Sortera på en redan
sorterad lista skulle det kräva samma antal steg som det
skulle när man kör över en helt osorterad lista.
Så val sortera har ett bästa fall prestanda n kvadrat,
som vi representerar med omega n kvadrat.
Och det är det för val sorterar.
Bara en av de många algoritmer vi can
använda för att sortera en lista.
Mitt namn är Tommy, och detta är CS50.