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