1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] Tommy: Låt oss ta en titt på val Sortera, en algoritm 2 00:00:09,980 --> 00:00:12,800 för att ta en lista med tal och sortera dem. 3 00:00:12,800 --> 00:00:15,750 En algoritm, kom ihåg, är helt enkelt ett steg-för-steg 4 00:00:15,750 --> 00:00:18,370 förfarande för att åstadkomma en uppgift. 5 00:00:18,370 --> 00:00:21,470 Den grundläggande idén bakom val Sortera är att dela 6 00:00:21,470 --> 00:00:23,390 vår lista i två delar - 7 00:00:23,390 --> 00:00:26,810 en sorterad del och en osorterad parti. 8 00:00:26,810 --> 00:00:30,200 Vid varje steg i algoritmen, är ett nummer flyttas från 9 00:00:30,200 --> 00:00:33,800 osorterat parti till den sorterade delen tills slutligen 10 00:00:33,800 --> 00:00:35,880 Hela listan är sorterad. 11 00:00:35,880 --> 00:00:38,510 Så här är en lista över sex nummer - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, och 15. 13 00:00:44,010 --> 00:00:47,680 Just nu hela listan anses osorterat. 14 00:00:47,680 --> 00:00:51,770 Även om ett antal som 16 kanske redan i sitt rätta 15 00:00:51,770 --> 00:00:56,040 plats, har vår algoritm inte kan veta att tills 16 00:00:56,040 --> 00:00:57,980 Hela listan är sorterad. 17 00:00:57,980 --> 00:01:01,355 Så vi ska överväga varje nummer som ska osorterade tills vi sorterar 18 00:01:01,355 --> 00:01:03,800 det själva. 19 00:01:03,800 --> 00:01:06,890 Vi vet att vi vill att listan ska vara i stigande ordning. 20 00:01:06,890 --> 00:01:10,200 Så vi kommer att vilja bygga upp den sorterade delen av vår lista 21 00:01:10,200 --> 00:01:13,280 från vänster till höger, minsta till det största. 22 00:01:13,280 --> 00:01:17,970 För att göra det, vi måste hitta den minsta osorterade elementet 23 00:01:17,970 --> 00:01:21,350 och lägga den i slutet av den sorterade delen. 24 00:01:21,350 --> 00:01:25,370 Eftersom denna lista inte är sorterad, är det enda sättet att göra det på 25 00:01:25,370 --> 00:01:29,330 titta på varje element i osorterade delen, minns 26 00:01:29,330 --> 00:01:32,010 vilket element är den lägsta och jämföra 27 00:01:32,010 --> 00:01:33,770 varje element till det. 28 00:01:33,770 --> 00:01:36,150 Så vi ska först titta på 23. 29 00:01:36,150 --> 00:01:38,650 Detta är det första elementet som vi har sett, så vi kommer ihåg 30 00:01:38,650 --> 00:01:40,050 det som ett minimum. 31 00:01:40,050 --> 00:01:42,320 Nästa vi titta på 42. 32 00:01:42,320 --> 00:01:46,720 42 är större än 23, så 23 är fortfarande ett minimum. 33 00:01:46,720 --> 00:01:51,210 Nästa är 4 som är mindre än 23, så vi kommer ihåg 4 34 00:01:51,210 --> 00:01:52,880 som det nya minimivärdet. 35 00:01:52,880 --> 00:01:56,380 Nästa är 16 som är större än 4, så 4 36 00:01:56,380 --> 00:01:57,980 är fortfarande ett minimum. 37 00:01:57,980 --> 00:02:03,670 8 är större än 4, och 15 är större än 4, så 4 måste vara 38 00:02:03,670 --> 00:02:05,980 det minsta elementet osorterat. 39 00:02:05,980 --> 00:02:09,350 Så även om som människor kan vi genast se att 4 är 40 00:02:09,350 --> 00:02:12,300 minsta elementet, måste vår algoritm för att titta på 41 00:02:12,300 --> 00:02:15,710 Varje osorterade element även efter att vi har hittat 4 - 42 00:02:15,710 --> 00:02:16,860 minsta elementet. 43 00:02:16,860 --> 00:02:19,900 Så nu när vi har hittat den minsta delen, 4, vi vill 44 00:02:19,900 --> 00:02:23,410 att flytta den till den sorterade delen av listan. 45 00:02:23,410 --> 00:02:27,320 Eftersom detta är det första steget innebär detta att vi vill sätta 4 på 46 00:02:27,320 --> 00:02:29,680 början av listan. 47 00:02:29,680 --> 00:02:33,040 Just nu 23 är i början av listan, så 48 00:02:33,040 --> 00:02:36,080 låt oss byta 4 och 23. 49 00:02:36,080 --> 00:02:38,870 Så nu vår lista ser ut så här. 50 00:02:38,870 --> 00:02:42,710 Vi vet att 4 skall vara i sitt slutliga läge, eftersom det är 51 00:02:42,710 --> 00:02:45,890 både det minsta elementet och elementet i början 52 00:02:45,890 --> 00:02:46,960 i listan. 53 00:02:46,960 --> 00:02:50,650 Så detta betyder att vi inte skulle behöva flytta igen. 54 00:02:50,650 --> 00:02:53,910 Så låt oss upprepa denna process för att lägga till ytterligare element till 55 00:02:53,910 --> 00:02:55,910 sorterade delen av listan. 56 00:02:55,910 --> 00:02:58,950 Vi vet att vi inte behöver titta på 4, eftersom det är 57 00:02:58,950 --> 00:03:00,000 redan sorterade. 58 00:03:00,000 --> 00:03:03,540 Så vi kan börja på 42, ​​vilket vi kommer ihåg som 59 00:03:03,540 --> 00:03:05,290 minsta elementet. 60 00:03:05,290 --> 00:03:08,700 Så nästa ska vi titta på den 23 som är mindre än 42, så vi 61 00:03:08,700 --> 00:03:11,620 minns 23 är den nya miniminivån. 62 00:03:11,620 --> 00:03:14,870 Nästa vi ser 16 som är mindre än 23, så 63 00:03:14,870 --> 00:03:16,800 16 är det nya minimum. 64 00:03:16,800 --> 00:03:19,720 Nu får vi titta på 8 som är mindre än 16, så 65 00:03:19,720 --> 00:03:21,130 8 är den nya minsta. 66 00:03:21,130 --> 00:03:25,900 Och slutligen 8 är mindre än 15, så vi vet att 8 är ett minimum 67 00:03:25,900 --> 00:03:27,780 osorterat elementet. 68 00:03:27,780 --> 00:03:30,660 Så det innebär att vi bör lägga 8 till den sorterade 69 00:03:30,660 --> 00:03:32,450 delen av listan. 70 00:03:32,450 --> 00:03:35,990 Just nu 4 är den enda sorterade elementet, så vi vill placera 71 00:03:35,990 --> 00:03:38,410 den 8 bredvid 4. 72 00:03:38,410 --> 00:03:41,920 Sedan 42 är det första elementet i den osorterade delen av 73 00:03:41,920 --> 00:03:47,260 listan, vi vill byta 42 och 8. 74 00:03:47,260 --> 00:03:49,680 Så nu vår lista ser ut så här. 75 00:03:49,680 --> 00:03:53,830 4 och 8 representerar den sorterade delen av listan, och den 76 00:03:53,830 --> 00:03:56,440 resterade siffrorna representerar osorterade 77 00:03:56,440 --> 00:03:58,260 delen av listan. 78 00:03:58,260 --> 00:04:00,630 Så låt oss fortsätta med en annan iteration. 79 00:04:00,630 --> 00:04:03,850 Vi börjar med 23 den här gången, eftersom vi inte behöver titta på 80 00:04:03,850 --> 00:04:05,770 den 4 och 8 längre eftersom de har 81 00:04:05,770 --> 00:04:07,660 redan sorterats. 82 00:04:07,660 --> 00:04:10,270 16 är mindre än 23, så vi kommer ihåg 83 00:04:10,270 --> 00:04:12,070 16 som det nya minimivärdet. 84 00:04:12,070 --> 00:04:18,149 16 är mindre än 42, men 15 är mindre än 16, så 15 måste vara 85 00:04:18,149 --> 00:04:20,480 minsta osorterat elementet. 86 00:04:20,480 --> 00:04:24,580 Så nu vill vi byta 15 och 23 till 87 00:04:24,580 --> 00:04:26,310 ge oss den här listan. 88 00:04:26,310 --> 00:04:30,500 Den sorterade delen av listan består av 4, 8 och 15, samt 89 00:04:30,500 --> 00:04:33,210 dessa element är fortfarande osorterade. 90 00:04:33,210 --> 00:04:36,900 Men det råkar vara så att nästa osorterade element, 16, 91 00:04:36,900 --> 00:04:38,480 är redan sorterade. 92 00:04:38,480 --> 00:04:42,060 Men det finns inget sätt för vår algoritm för att veta att 16 93 00:04:42,060 --> 00:04:45,230 är redan i sin rätta plats, så vi måste fortfarande 94 00:04:45,230 --> 00:04:47,870 upprepa exakt samma process. 95 00:04:47,870 --> 00:04:53,750 Så vi ser att 16 är mindre än 42, och 16 är mindre än 23, så 96 00:04:53,750 --> 00:04:56,230 16 måste vara det minsta elementet. 97 00:04:56,230 --> 00:04:59,010 Det är omöjligt att byta denna del med sig själv, så att vi kan 98 00:04:59,010 --> 00:05:01,780 bara lämna det på den här platsen. 99 00:05:01,780 --> 00:05:04,660 Så vi behöver en mer pass av vår algoritm. 100 00:05:04,660 --> 00:05:09,370 42 är större än 23, så 23 måste vara 101 00:05:09,370 --> 00:05:10,970 minsta osorterade elementet. 102 00:05:10,970 --> 00:05:17,410 När vi byta 23 och 42, vi sluta med vår sista 103 00:05:17,410 --> 00:05:18,530 sorterad lista - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Vi vet 42 måste vara på rätt plats eftersom det är den 106 00:05:26,830 --> 00:05:30,210 enda elementet kvar, och det är val Sortera. 107 00:05:30,210 --> 00:05:32,100 Låt oss formalisera nu vår algoritm med några 108 00:05:32,100 --> 00:05:34,540 pseudokod. 109 00:05:34,540 --> 00:05:37,760 På rad ett, kan vi se att vi behöver integrera över 110 00:05:37,760 --> 00:05:39,530 varje element i listan. 111 00:05:39,530 --> 00:05:42,150 Utom det sista elementet, eftersom 1 element 112 00:05:42,150 --> 00:05:44,230 Listan är redan sorterad. 113 00:05:44,230 --> 00:05:48,100 På rad två, anser vi det första elementet i osorterade 114 00:05:48,100 --> 00:05:51,080 del av listan är det minsta, som vi gjorde med vår 115 00:05:51,080 --> 00:05:53,750 exempel, så vi har något att jämföra med. 116 00:05:53,750 --> 00:05:57,260 Linje tre börjar en andra slinga där vi iterera över 117 00:05:57,260 --> 00:05:59,170 varje osorterade element. 118 00:05:59,170 --> 00:06:02,150 Vi vet att när jag iterationer, den sorterade delen 119 00:06:02,150 --> 00:06:05,330 på vår lista måste jag element i det eftersom varje steg 120 00:06:05,330 --> 00:06:06,890 sorterar ett element. 121 00:06:06,890 --> 00:06:11,770 Så det första osorterade elementet måste vara i läge I plus 1. 122 00:06:11,770 --> 00:06:15,440 På rad fyra, jämför vi det aktuella elementet till ett minimum 123 00:06:15,440 --> 00:06:17,750 element som vi har sett hittills. 124 00:06:17,750 --> 00:06:20,560 Om det aktuella elementet är mindre än den minsta 125 00:06:20,560 --> 00:06:23,870 inslag, då vi minns det aktuella elementet som ny 126 00:06:23,870 --> 00:06:26,250 minimum på linje fem. 127 00:06:26,250 --> 00:06:29,900 Slutligen, på rad sex och sju, byta vi det minsta 128 00:06:29,900 --> 00:06:33,080 element med det första osorterade elementet, vilket 129 00:06:33,080 --> 00:06:36,990 lägga till det i den sorterade delen av listan. 130 00:06:36,990 --> 00:06:40,030 När vi har en algoritm, en viktig fråga ställa 131 00:06:40,030 --> 00:06:43,370 oss som programmerare är hur lång tid tog det att ta? 132 00:06:43,370 --> 00:06:46,970 Vi kommer först fråga frågan hur lång tid tar det för 133 00:06:46,970 --> 00:06:50,070 algoritm för att köra i värsta fall? 134 00:06:50,070 --> 00:06:51,640 Minns vi representerar denna gång 135 00:06:51,640 --> 00:06:55,060 tid med Big O notation. 136 00:06:55,060 --> 00:06:58,650 För att bestämma den minsta osorterade elementet, vi 137 00:06:58,650 --> 00:07:01,880 huvudsak hade att jämföra varje element i listan för att 138 00:07:01,880 --> 00:07:04,040 varannan element i listan. 139 00:07:04,040 --> 00:07:08,430 Intuitivt, detta låter som en O n kvadrat drift. 140 00:07:08,430 --> 00:07:12,050 Titta på vår pseudokod, har vi också en slinga kapslat 141 00:07:12,050 --> 00:07:14,420 annan slinga, som verkligen låter som en O 142 00:07:14,420 --> 00:07:16,480 n kvadrat drift. 143 00:07:16,480 --> 00:07:19,250 Kom dock ihåg att vi inte behövde se över 144 00:07:19,250 --> 00:07:23,460 Hela listan vid fastställandet av minsta osorterade element? 145 00:07:23,460 --> 00:07:26,600 När vi visste att 4 var sorterade, till exempel, gjorde vi inte 146 00:07:26,600 --> 00:07:28,170 behöver titta på det igen. 147 00:07:28,170 --> 00:07:31,020 Det gör det lägre gångtid? 148 00:07:31,020 --> 00:07:34,510 För vår lista över längden 6, behövde vi göra fem 149 00:07:34,510 --> 00:07:37,990 jämförelser för det första elementet, fyra jämförelser för 150 00:07:37,990 --> 00:07:40,750 det andra elementet, och så vidare. 151 00:07:40,750 --> 00:07:44,690 Det innebär att det totala antalet steg är summan av 152 00:07:44,690 --> 00:07:49,160 heltalen från 1 till längden av listan minus 1. 153 00:07:49,160 --> 00:07:51,005 Vi kan representera detta med en summering. 154 00:07:57,980 --> 00:07:59,910 Vi kommer inte att gå in summeringar här. 155 00:07:59,910 --> 00:08:04,900 Men det visar sig att denna summering är lika med n gånger 156 00:08:04,900 --> 00:08:07,540 n minus 1 över 2. 157 00:08:07,540 --> 00:08:14,220 Eller ekvivalent n kvadrerade över 2 minus n över 2. 158 00:08:14,220 --> 00:08:18,860 När man talar om asymptotisk runtime, detta N kvadrerade termen 159 00:08:18,860 --> 00:08:22,070 kommer att dominera denna N sikt. 160 00:08:22,070 --> 00:08:27,850 Så val typ är O n kvadrat. 161 00:08:27,850 --> 00:08:31,460 Minns att i vårt exempel, val Sortera fortfarande behövde 162 00:08:31,460 --> 00:08:33,850 kontrollera om ett nummer som redan sorterades 163 00:08:33,850 --> 00:08:35,450 behövde flyttas. 164 00:08:35,450 --> 00:08:38,929 Så det betyder att om vi körde val Sortera på en redan 165 00:08:38,929 --> 00:08:43,070 sorterad lista skulle det kräva samma antal steg som det 166 00:08:43,070 --> 00:08:46,340 skulle när man kör över en helt osorterad lista. 167 00:08:46,340 --> 00:08:51,470 Så val sortera har ett bästa fall prestanda n kvadrat, 168 00:08:51,470 --> 00:08:56,820 som vi representerar med omega n kvadrat. 169 00:08:56,820 --> 00:08:58,600 Och det är det för val sorterar. 170 00:08:58,600 --> 00:09:00,630 Bara en av de många algoritmer vi can 171 00:09:00,630 --> 00:09:02,390 använda för att sortera en lista. 172 00:09:02,390 --> 00:09:05,910 Mitt namn är Tommy, och detta är CS50.