1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: La oss ta en titt på utvalget sortere, en algoritme 2 00:00:09,980 --> 00:00:12,800 for å ta en liste med tall og sortere dem. 3 00:00:12,800 --> 00:00:15,750 En algoritme, husk, det er rett og slett en steg-for-steg 4 00:00:15,750 --> 00:00:18,370 prosedyre for å utføre en oppgave. 5 00:00:18,370 --> 00:00:21,470 Den grunnleggende ideen bak valg slags er å dele 6 00:00:21,470 --> 00:00:23,390 vår liste i to deler - 7 00:00:23,390 --> 00:00:26,810 en sortert del og en usortert del. 8 00:00:26,810 --> 00:00:30,200 På hvert trinn av algoritmen, er et nummer flyttet fra 9 00:00:30,200 --> 00:00:33,800 usortert del til den sorterte delen før slutt 10 00:00:33,800 --> 00:00:35,880 Hele listen er sortert. 11 00:00:35,880 --> 00:00:38,510 Så her er en liste med seks tall - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, og 15. 13 00:00:44,010 --> 00:00:47,680 Akkurat nå hele listen regnes usortert. 14 00:00:47,680 --> 00:00:51,770 Selv om en rekke som 16 kan allerede være i korrekt 15 00:00:51,770 --> 00:00:56,040 beliggenhet, har vår algoritme ingen måte å vite at inntil 16 00:00:56,040 --> 00:00:57,980 Hele listen er sortert. 17 00:00:57,980 --> 00:01:01,355 Så vi vil vurdere hver for å bli usortert før vi sortere 18 00:01:01,355 --> 00:01:03,800 det selv. 19 00:01:03,800 --> 00:01:06,890 Vi vet at vi vil at listen skal være i stigende rekkefølge. 20 00:01:06,890 --> 00:01:10,200 Så vi ønsker å bygge opp den sorterte delen av vår liste 21 00:01:10,200 --> 00:01:13,280 fra venstre til høyre, minste til største. 22 00:01:13,280 --> 00:01:17,970 For å gjøre det, må vi finne minimum usortert element 23 00:01:17,970 --> 00:01:21,350 og sette den på slutten av den sorterte parti. 24 00:01:21,350 --> 00:01:25,370 Siden denne listen ikke er sortert, er den eneste måten å gjøre det til 25 00:01:25,370 --> 00:01:29,330 se på hvert element i usortert del, huske 26 00:01:29,330 --> 00:01:32,010 hvilket element er den laveste og sammenligne 27 00:01:32,010 --> 00:01:33,770 hvert element til det. 28 00:01:33,770 --> 00:01:36,150 Så vil vi først se på 23. 29 00:01:36,150 --> 00:01:38,650 Dette er det første elementet vi har sett, så vi vil huske 30 00:01:38,650 --> 00:01:40,050 det som minimum. 31 00:01:40,050 --> 00:01:42,320 Neste vi skal se på 42. 32 00:01:42,320 --> 00:01:46,720 42 er større enn 23, så 23 er fortsatt minimum. 33 00:01:46,720 --> 00:01:51,210 Neste er 4 som er mindre enn 23, så vi vil huske 4 34 00:01:51,210 --> 00:01:52,880 som den nye minimum. 35 00:01:52,880 --> 00:01:56,380 Neste er 16 som er større enn 4, så 4 36 00:01:56,380 --> 00:01:57,980 er fortsatt minimum. 37 00:01:57,980 --> 00:02:03,670 8 er større enn 4, og 15 er større enn 4, slik at 4 må være 38 00:02:03,670 --> 00:02:05,980 den minste usortert element. 39 00:02:05,980 --> 00:02:09,350 Så selv om som mennesker kan vi umiddelbart se at 4 er 40 00:02:09,350 --> 00:02:12,300 minimum element, trenger vår algoritme for å se på 41 00:02:12,300 --> 00:02:15,710 hver usortert element, selv etter at vi har funnet 4 - 42 00:02:15,710 --> 00:02:16,860 minimum element. 43 00:02:16,860 --> 00:02:19,900 Så nå som vi har funnet minimum element, 4, vil vi ønske 44 00:02:19,900 --> 00:02:23,410 å flytte det til den sorterte parti av listen. 45 00:02:23,410 --> 00:02:27,320 Siden dette er det første skrittet, dette betyr at vi ønsker å sette 4 på 46 00:02:27,320 --> 00:02:29,680 begynnelsen av listen. 47 00:02:29,680 --> 00:02:33,040 Akkurat nå 23 er ved begynnelsen av listen, så 48 00:02:33,040 --> 00:02:36,080 la oss bytte 4 og 23. 49 00:02:36,080 --> 00:02:38,870 Så nå vår liste ser slik ut. 50 00:02:38,870 --> 00:02:42,710 Vi vet at 4 må være i sin endelige plassering, fordi det er 51 00:02:42,710 --> 00:02:45,890 både minste element og elementet i begynnelsen 52 00:02:45,890 --> 00:02:46,960 av listen. 53 00:02:46,960 --> 00:02:50,650 Så dette betyr at vi ikke trenger å flytte den igjen. 54 00:02:50,650 --> 00:02:53,910 Så la oss gjenta denne prosessen for å legge et annet element til 55 00:02:53,910 --> 00:02:55,910 sorteres parti av listen. 56 00:02:55,910 --> 00:02:58,950 Vi vet at vi ikke trenger å se på 4, fordi det er 57 00:02:58,950 --> 00:03:00,000 allerede sortert. 58 00:03:00,000 --> 00:03:03,540 Så vi kan starte på 42, ​​som vi vil huske som 59 00:03:03,540 --> 00:03:05,290 minimum element. 60 00:03:05,290 --> 00:03:08,700 Så neste vi skal se på de 23 som er mindre enn 42, så vi 61 00:03:08,700 --> 00:03:11,620 huske 23 er den nye minimum. 62 00:03:11,620 --> 00:03:14,870 Neste vi ser 16 som er mindre enn 23, så 63 00:03:14,870 --> 00:03:16,800 16 er den nye minimum. 64 00:03:16,800 --> 00:03:19,720 Nå ser vi på de 8 som er mindre enn 16, så 65 00:03:19,720 --> 00:03:21,130 8 er den nye minimum. 66 00:03:21,130 --> 00:03:25,900 Og til slutt 8 er mindre enn 15, slik at vi vet at 8 er et minimum 67 00:03:25,900 --> 00:03:27,780 usortert element. 68 00:03:27,780 --> 00:03:30,660 Så det betyr at vi bør legge 8 til den sorterte 69 00:03:30,660 --> 00:03:32,450 del av listen. 70 00:03:32,450 --> 00:03:35,990 Akkurat nå 4 er den eneste sortert element, så vi ønsker å plassere 71 00:03:35,990 --> 00:03:38,410 de 8 ved siden av 4. 72 00:03:38,410 --> 00:03:41,920 Siden 42 er det første elementet i den usortert delen av 73 00:03:41,920 --> 00:03:47,260 listen, vil vi ønske å bytte 42 og 8. 74 00:03:47,260 --> 00:03:49,680 Så nå vår liste ser slik ut. 75 00:03:49,680 --> 00:03:53,830 4 og 8 representerer den sorterte parti av listen, og den 76 00:03:53,830 --> 00:03:56,440 resten av tallene representerer usortert 77 00:03:56,440 --> 00:03:58,260 del av listen. 78 00:03:58,260 --> 00:04:00,630 Så la oss fortsette med en annen iterasjon. 79 00:04:00,630 --> 00:04:03,850 Vi starter med 23 denne gangen, siden vi ikke trenger å se på 80 00:04:03,850 --> 00:04:05,770 de 4 og 8 lenger fordi de har 81 00:04:05,770 --> 00:04:07,660 allerede blitt sortert. 82 00:04:07,660 --> 00:04:10,270 16 er mindre enn 23, så vi vil huske 83 00:04:10,270 --> 00:04:12,070 16 som den nye minimum. 84 00:04:12,070 --> 00:04:18,149 16 er mindre enn 42, men 15 er mindre enn 16, så 15 må 85 00:04:18,149 --> 00:04:20,480 minimum usortert element. 86 00:04:20,480 --> 00:04:24,580 Så nå ønsker vi å bytte 15 og 23 til 87 00:04:24,580 --> 00:04:26,310 gi oss denne listen. 88 00:04:26,310 --> 00:04:30,500 Sorterte parti av listen består av 4, 8 og 15, og 89 00:04:30,500 --> 00:04:33,210 disse elementene er fortsatt usortert. 90 00:04:33,210 --> 00:04:36,900 Men det bare skjer, slik at neste usortert element, 16, 91 00:04:36,900 --> 00:04:38,480 er allerede sortert. 92 00:04:38,480 --> 00:04:42,060 Men det er ingen måte for algoritmen vår å vite at 16 93 00:04:42,060 --> 00:04:45,230 er allerede i sin riktig sted, slik at vi fortsatt trenger å 94 00:04:45,230 --> 00:04:47,870 gjentar nøyaktig den samme prosessen. 95 00:04:47,870 --> 00:04:53,750 Således ser vi at 16 er mindre enn 42, og 16 er mindre enn 23, så 96 00:04:53,750 --> 00:04:56,230 16 må være det minst element. 97 00:04:56,230 --> 00:04:59,010 Det er umulig å bytte dette elementet med seg selv, slik at vi kan 98 00:04:59,010 --> 00:05:01,780 bare la det i denne plasseringen. 99 00:05:01,780 --> 00:05:04,660 Så vi trenger en mer pass algoritmen vår. 100 00:05:04,660 --> 00:05:09,370 42 er større enn 23, så 23 må være den 101 00:05:09,370 --> 00:05:10,970 minimum usortert element. 102 00:05:10,970 --> 00:05:17,410 Når vi bytte 23 og 42, vi ender opp med vår endelige 103 00:05:17,410 --> 00:05:18,530 sortert liste - 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å være på riktig sted siden det er den 106 00:05:26,830 --> 00:05:30,210 eneste elementet igjen, og det er valg slag. 107 00:05:30,210 --> 00:05:32,100 La oss nå formalisere vår algoritme med noen 108 00:05:32,100 --> 00:05:34,540 pseudokode. 109 00:05:34,540 --> 00:05:37,760 På linje en, kan vi se at vi trenger å integrere over 110 00:05:37,760 --> 00:05:39,530 hvert element i listen. 111 00:05:39,530 --> 00:05:42,150 Unntatt siste elementet, siden 1 elementet 112 00:05:42,150 --> 00:05:44,230 listen er allerede sortert. 113 00:05:44,230 --> 00:05:48,100 På linje to, anser vi det første elementet i usorterte 114 00:05:48,100 --> 00:05:51,080 del av listen for å være den minste, som vi gjorde med vår 115 00:05:51,080 --> 00:05:53,750 eksempel, så vi har noe å sammenligne med. 116 00:05:53,750 --> 00:05:57,260 Linje tre begynner en ny sløyfe som vi iterere over 117 00:05:57,260 --> 00:05:59,170 hver usortert element. 118 00:05:59,170 --> 00:06:02,150 Vi vet at etter at jeg gjentakelser, den sorterte delen 119 00:06:02,150 --> 00:06:05,330 av vår liste må jeg har elementer i seg siden hvert trinn 120 00:06:05,330 --> 00:06:06,890 sorterer ett element. 121 00:06:06,890 --> 00:06:11,770 Så det første usortert element må være i posisjon i pluss 1. 122 00:06:11,770 --> 00:06:15,440 På linje fire, sammenligner vi det aktuelle elementet til minimum 123 00:06:15,440 --> 00:06:17,750 element som vi har sett så langt. 124 00:06:17,750 --> 00:06:20,560 Hvis gjeldende element er mindre enn minimum 125 00:06:20,560 --> 00:06:23,870 element, så vi husker den gjeldende element som ny 126 00:06:23,870 --> 00:06:26,250 minimum på linje fem. 127 00:06:26,250 --> 00:06:29,900 Til slutt, på linje seks og sju, bytte vi minimum 128 00:06:29,900 --> 00:06:33,080 element med første usortert elementet, og dermed 129 00:06:33,080 --> 00:06:36,990 å legge den til den sorterte parti av listen. 130 00:06:36,990 --> 00:06:40,030 Når vi har en algoritme, til et viktig spørsmål spør 131 00:06:40,030 --> 00:06:43,370 oss som programmerere er hvor lang tid tok det ta? 132 00:06:43,370 --> 00:06:46,970 Vi vil først stille spørsmålet hvor lang tid tar det for dette 133 00:06:46,970 --> 00:06:50,070 algoritme for å kjøre i verste fall? 134 00:06:50,070 --> 00:06:51,640 Husker vi representerer dette kjører 135 00:06:51,640 --> 00:06:55,060 tid med stor O-notasjon. 136 00:06:55,060 --> 00:06:58,650 For å bestemme minimum usortert element, vi 137 00:06:58,650 --> 00:07:01,880 egentlig hadde å sammenligne hvert element i listen for å 138 00:07:01,880 --> 00:07:04,040 annenhver element i listen. 139 00:07:04,040 --> 00:07:08,430 Intuitivt, dette høres ut som en O n squared drift. 140 00:07:08,430 --> 00:07:12,050 Ser på pseudokode vår, vi har også en sløyfe nestet inne 141 00:07:12,050 --> 00:07:14,420 en annen loop, som faktisk høres ut som en O 142 00:07:14,420 --> 00:07:16,480 av n kvadrert drift. 143 00:07:16,480 --> 00:07:19,250 Men husk at vi ikke trenger å se over 144 00:07:19,250 --> 00:07:23,460 hele listen ved fastsettelse av minimum usortert element? 145 00:07:23,460 --> 00:07:26,600 Når vi visste at 4 ble sortert, for eksempel, gjorde vi ikke 146 00:07:26,600 --> 00:07:28,170 trenger å se på det igjen. 147 00:07:28,170 --> 00:07:31,020 Så betyr dette lavere løpende tid? 148 00:07:31,020 --> 00:07:34,510 For vår liste over lengde 6, vi trengte å gjøre fem 149 00:07:34,510 --> 00:07:37,990 sammenligninger for det første elementet, fire sammenligninger for 150 00:07:37,990 --> 00:07:40,750 det andre elementet, og så videre. 151 00:07:40,750 --> 00:07:44,690 Det betyr at det totale antall trinn er summen av 152 00:07:44,690 --> 00:07:49,160 heltallene fra 1 til lengden av listen minus 1. 153 00:07:49,160 --> 00:07:51,005 Vi kan representere dette med en summering. 154 00:07:57,980 --> 00:07:59,910 Vi vil ikke gå inn summeringer her. 155 00:07:59,910 --> 00:08:04,900 Men det viser seg at dette summering er lik n ganger 156 00:08:04,900 --> 00:08:07,540 n minus 1 over 2. 157 00:08:07,540 --> 00:08:14,220 Eller ekvivalent, n squared over 2 minus n over 2. 158 00:08:14,220 --> 00:08:18,860 Når man snakker om asymptotisk kjøretid, dette n squared sikt 159 00:08:18,860 --> 00:08:22,070 kommer til å dominere denne n sikt. 160 00:08:22,070 --> 00:08:27,850 Så utvalg sort er O n squared. 161 00:08:27,850 --> 00:08:31,460 Husk at i vårt eksempel, valg slags fortsatt måtte 162 00:08:31,460 --> 00:08:33,850 sjekke om et tall som allerede var sortert 163 00:08:33,850 --> 00:08:35,450 trengs for å bli flyttet. 164 00:08:35,450 --> 00:08:38,929 Så det betyr at hvis vi kjørte valg slags over en allerede 165 00:08:38,929 --> 00:08:43,070 sortert liste, ville det kreve det samme antall trinn som det 166 00:08:43,070 --> 00:08:46,340 ville når du kjører over en helt usortert liste. 167 00:08:46,340 --> 00:08:51,470 Så utvalg sorter har best case ytelse av n kvadrat, 168 00:08:51,470 --> 00:08:56,820 som vi representerer med omega n squared. 169 00:08:56,820 --> 00:08:58,600 Og det er det for utvalget slag. 170 00:08:58,600 --> 00:09:00,630 Bare ett av de mange algoritmer vi kan 171 00:09:00,630 --> 00:09:02,390 bruke til å sortere en liste. 172 00:09:02,390 --> 00:09:05,910 Mitt navn er Tommy, og dette er CS50.