[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.