[Powered by Google Translate] TOMMY: La oss ta en titt på utvalget sortere, en algoritme for å ta en liste med tall og sortere dem. En algoritme, husk, det er rett og slett en steg-for-steg prosedyre for å utføre en oppgave. Den grunnleggende ideen bak valg slags er å dele vår liste i to deler - en sortert del og en usortert del. På hvert trinn av algoritmen, er et nummer flyttet fra usortert del til den sorterte delen før slutt Hele listen er sortert. Så her er en liste med seks tall - 23, 42, 4, 16, 8, og 15. Akkurat nå hele listen regnes usortert. Selv om en rekke som 16 kan allerede være i korrekt beliggenhet, har vår algoritme ingen måte å vite at inntil Hele listen er sortert. Så vi vil vurdere hver for å bli usortert før vi sortere det selv. Vi vet at vi vil at listen skal være i stigende rekkefølge. Så vi ønsker å bygge opp den sorterte delen av vår liste fra venstre til høyre, minste til største. For å gjøre det, må vi finne minimum usortert element og sette den på slutten av den sorterte parti. Siden denne listen ikke er sortert, er den eneste måten å gjøre det til se på hvert element i usortert del, huske hvilket element er den laveste og sammenligne hvert element til det. Så vil vi først se på 23. Dette er det første elementet vi har sett, så vi vil huske det som minimum. Neste vi skal se på 42. 42 er større enn 23, så 23 er fortsatt minimum. Neste er 4 som er mindre enn 23, så vi vil huske 4 som den nye minimum. Neste er 16 som er større enn 4, så 4 er fortsatt minimum. 8 er større enn 4, og 15 er større enn 4, slik at 4 må være den minste usortert element. Så selv om som mennesker kan vi umiddelbart se at 4 er minimum element, trenger vår algoritme for å se på hver usortert element, selv etter at vi har funnet 4 - minimum element. Så nå som vi har funnet minimum element, 4, vil vi ønske å flytte det til den sorterte parti av listen. Siden dette er det første skrittet, dette betyr at vi ønsker å sette 4 på begynnelsen av listen. Akkurat nå 23 er ved begynnelsen av listen, så la oss bytte 4 og 23. Så nå vår liste ser slik ut. Vi vet at 4 må være i sin endelige plassering, fordi det er både minste element og elementet i begynnelsen av listen. Så dette betyr at vi ikke trenger å flytte den igjen. Så la oss gjenta denne prosessen for å legge et annet element til sorteres parti av listen. Vi vet at vi ikke trenger å se på 4, fordi det er allerede sortert. Så vi kan starte på 42, ​​som vi vil huske som minimum element. Så neste vi skal se på de 23 som er mindre enn 42, så vi huske 23 er den nye minimum. Neste vi ser 16 som er mindre enn 23, så 16 er den nye minimum. Nå ser vi på de 8 som er mindre enn 16, så 8 er den nye minimum. Og til slutt 8 er mindre enn 15, slik at vi vet at 8 er et minimum usortert element. Så det betyr at vi bør legge 8 til den sorterte del av listen. Akkurat nå 4 er den eneste sortert element, så vi ønsker å plassere de 8 ved siden av 4. Siden 42 er det første elementet i den usortert delen av listen, vil vi ønske å bytte 42 og 8. Så nå vår liste ser slik ut. 4 og 8 representerer den sorterte parti av listen, og den resten av tallene representerer usortert del av listen. Så la oss fortsette med en annen iterasjon. Vi starter med 23 denne gangen, siden vi ikke trenger å se på de 4 og 8 lenger fordi de har allerede blitt sortert. 16 er mindre enn 23, så vi vil huske 16 som den nye minimum. 16 er mindre enn 42, men 15 er mindre enn 16, så 15 må minimum usortert element. Så nå ønsker vi å bytte 15 og 23 til gi oss denne listen. Sorterte parti av listen består av 4, 8 og 15, og disse elementene er fortsatt usortert. Men det bare skjer, slik at neste usortert element, 16, er allerede sortert. Men det er ingen måte for algoritmen vår å vite at 16 er allerede i sin riktig sted, slik at vi fortsatt trenger å gjentar nøyaktig den samme prosessen. Således ser vi at 16 er mindre enn 42, og 16 er mindre enn 23, så 16 må være det minst element. Det er umulig å bytte dette elementet med seg selv, slik at vi kan bare la det i denne plasseringen. Så vi trenger en mer pass algoritmen vår. 42 er større enn 23, så 23 må være den minimum usortert element. Når vi bytte 23 og 42, vi ender opp med vår endelige sortert liste - 4, 8, 15, 16, 23, 42. Vi vet 42 må være på riktig sted siden det er den eneste elementet igjen, og det er valg slag. La oss nå formalisere vår algoritme med noen pseudokode. På linje en, kan vi se at vi trenger å integrere over hvert element i listen. Unntatt siste elementet, siden 1 elementet listen er allerede sortert. På linje to, anser vi det første elementet i usorterte del av listen for å være den minste, som vi gjorde med vår eksempel, så vi har noe å sammenligne med. Linje tre begynner en ny sløyfe som vi iterere over hver usortert element. Vi vet at etter at jeg gjentakelser, den sorterte delen av vår liste må jeg har elementer i seg siden hvert trinn sorterer ett element. Så det første usortert element må være i posisjon i pluss 1. På linje fire, sammenligner vi det aktuelle elementet til minimum element som vi har sett så langt. Hvis gjeldende element er mindre enn minimum element, så vi husker den gjeldende element som ny minimum på linje fem. Til slutt, på linje seks og sju, bytte vi minimum element med første usortert elementet, og dermed å legge den til den sorterte parti av listen. Når vi har en algoritme, til et viktig spørsmål spør oss som programmerere er hvor lang tid tok det ta? Vi vil først stille spørsmålet hvor lang tid tar det for dette algoritme for å kjøre i verste fall? Husker vi representerer dette kjører tid med stor O-notasjon. For å bestemme minimum usortert element, vi egentlig hadde å sammenligne hvert element i listen for å annenhver element i listen. Intuitivt, dette høres ut som en O n squared drift. Ser på pseudokode vår, vi har også en sløyfe nestet inne en annen loop, som faktisk høres ut som en O av n kvadrert drift. Men husk at vi ikke trenger å se over hele listen ved fastsettelse av minimum usortert element? Når vi visste at 4 ble sortert, for eksempel, gjorde vi ikke trenger å se på det igjen. Så betyr dette lavere løpende tid? For vår liste over lengde 6, vi trengte å gjøre fem sammenligninger for det første elementet, fire sammenligninger for det andre elementet, og så videre. Det betyr at det totale antall trinn er summen av heltallene fra 1 til lengden av listen minus 1. Vi kan representere dette med en summering. Vi vil ikke gå inn summeringer her. Men det viser seg at dette summering er lik n ganger n minus 1 over 2. Eller ekvivalent, n squared over 2 minus n over 2. Når man snakker om asymptotisk kjøretid, dette n squared sikt kommer til å dominere denne n sikt. Så utvalg sort er O n squared. Husk at i vårt eksempel, valg slags fortsatt måtte sjekke om et tall som allerede var sortert trengs for å bli flyttet. Så det betyr at hvis vi kjørte valg slags over en allerede sortert liste, ville det kreve det samme antall trinn som det ville når du kjører over en helt usortert liste. Så utvalg sorter har best case ytelse av n kvadrat, som vi representerer med omega n squared. Og det er det for utvalget slag. Bare ett av de mange algoritmer vi kan bruke til å sortere en liste. Mitt navn er Tommy, og dette er CS50.