[Powered by Google Translate] TOMMY: Lad os tage et kig på udvælgelse slags, en algoritme
for at tage en liste over numre og sortere dem.
En algoritme, husk, er simpelthen en trin-for-trin
procedure for opstilling af en opgave.
Den grundlæggende idé bag udvælgelsen slags er at opdele
vores liste i to dele -
en sorteret del og en usorteret portion.
På hvert trin af algoritmen, er et tal flyttes fra
usorteret del til den sorterede del, indtil i sidste ende
Hele listen er sorteret.
Så her er en liste med seks numre -
23, 42, 4, 16, 8 og 15.
Lige nu hele listen anses usorteret.
Selv om en række som 16 kan allerede være i sin rette
placering, vores algoritme har ingen mulighed for at vide, at indtil
Hele listen er sorteret.
Så vi vil overveje alle tal, der skal usorteret indtil vi sorterer
det os.
Vi ved, at vi ønsker, at listen skal være i stigende orden.
Så vi vil gerne opbygge det sorterede del af vores liste
fra venstre mod højre, mindst til størst.
For at gøre det, vil vi nødt til at finde den mindste usorteret element
og sætte det i slutningen af ​​det sorterede portion.
Da denne liste ikke er sorteret, den eneste måde at gøre det er at
se på hvert element i den usorterede del, huske
hvilket element er det laveste og sammenligne
hvert element i denne.
Så vi vil først se på den 23.
Dette er det første element, vi har set, så vi vil huske
det som minimum.
Næste vil vi se på 42.
42 er større end 23, så 23 stadig et minimum.
Næste er den 4, som er mindre end 23, så vi vil huske 4
som den nye minimum.
Next er 16, som er større end 4, således 4
er stadig et minimum.
8 er større end 4, og 15 er større end 4, således 4 skal være
den mindste usorteret element.
Så selvom vi som mennesker kan straks se, at 4 er
den mindste del, vores algoritme nødvendigt at se på
hver usorterede element, selv efter at vi har fundet den 4 -
minimum element.
Så nu, at vi har fundet den mindste element, 4, vil vi gerne
at flytte den i den sorterede del af listen.
Da dette er det første skridt, det betyder, at vi ønsker at sætte 4 på
begyndelsen af ​​listen.
Lige nu 23 er i begyndelsen af ​​listen, så
lad os bytte 4 og 23.
Så nu vores liste ser sådan ud.
Vi ved, at 4 skal være i sin endelige placering, fordi det er
både det mindste element og elementet i begyndelsen
af listen.
Så det betyder, at vi ikke får brug for at flytte den igen.
Så lad os gentage denne proces for at tilføje endnu et element til den
sorteret del af listen.
Vi ved, at vi ikke behøver at se på 4, fordi det er
allerede sorteret.
Så vi kan starte på 42, ​​som vi vil huske som den
minimum element.
Så næste vi vil se på 23, som er mindre end 42, så vi
Husk 23 er det nye minimum.
Næste vi ser 16, som er mindre end 23, så
16 er det nye minimum.
Nu skal vi se på de 8, som er mindre end 16, så
8 er den nye minimum.
Og endelig 8 er mindre end 15, så vi ved, 8 er et minimum
usorteret element.
Så det betyder, at vi bør tilføje 8 til det sorterede
del af listen.
Lige nu 4 er det eneste sorteres element, så vi ønsker at placere
de 8 ved siden af ​​4.
Idet 42 er det første element i den usorterede del af
liste, vil vi ønsker at bytte den 42 og den 8.
Så nu vores liste ser sådan ud.
4 og 8 repræsenterer sorteret del af listen, og
resterende tal repræsenterer usorteret
del af listen.
Så lad os fortsætte med en anden iteration.
Vi starter med 23 denne gang, da vi ikke behøver at se på
Den 4 og 8 længere, fordi de har
allerede blevet sorteret.
16 er under 23, så vi vil huske
16 som den nye minimum.
16 er mindre end 42, men 15 er mindre end 16, så 15 skal være
den minimale usorteret element.
Så nu er vi ønsker at bytte de 15 og 23 til
give os denne liste.
Den sorterede portion af listen består af 4, 8 og 15, og
disse elementer er stadig usorteret.
Men det bare så sker det, at den næste usorteret element, 16,
allerede sorteret.
Men der er ingen måde for vores algoritme til at vide, at 16
er allerede i sin korrekte placering, så vi stadig nødt til at
gentages nøjagtig samme proces.
Så vi se, at 16 er mindre end 42, og 16 er mindre end 23, så
16 skal være den mindste element.
Det er umuligt at bytte dette element med sig selv, så vi kan
blot lade det på denne placering.
Så vi har brug for endnu en pass af vores algoritme.
42 er over 23, så 23 skal være
mindst usorteret element.
Når vi bytte 23 og 42, ender vi med vores endelige
sorteret liste -
4, 8, 15, 16, 23, 42.
Vi ved 42 skal være på det rigtige sted, da det er den
eneste element tilbage, og det er udvælgelse slags.
Lad os nu formalisere vores algoritme med nogle
pseudokode.
På linje et, kan vi se, at vi er nødt til at integrere i
hvert element på listen.
Undtagen det sidste element, idet 1 element
Listen er allerede sorteret.
I linje to, betragter vi det første element i den usorterede
del af listen for at være det minimum, som vi gjorde med vores
eksempel, så vi har noget at sammenligne med.
Linje tre begynder en anden sløjfe, hvor vi gentage over
hvert usorteret element.
Vi ved, at efter jeg iterationer, den sorterede portion
på vores liste, skal jeg har elementer i det, da hvert trin
sorterer ét element.
Så det første usorteret element skal være i position I plus 1.
I linje fire, sammenligner vi det aktuelle element til et minimum
element, som vi har set hidtil.
Hvis det aktuelle element er mindre end den mindste
element, så vi husker det aktuelle element som ny
minimum på linje fem.
Endelig på linje seks og syv, bytte vi det minimum
element med det første usorterede element, hvorved
at føje den til sorteret del af listen.
Når vi har en algoritme, til et vigtigt spørgsmål spørge
os selv som programmører er hvor lang tid tog det tage?
Vi vil først spørge, hvor lang tid tager det for denne
algoritme til at køre i værste fald?
Husker vi repræsenterer dette løb
tid med store O notation.
For at bestemme den minimale usorteret element, vi
hovedsageligt skulle sammenligne hvert element på listen for at
hver andet element i listen.
Intuitivt dette lyder som en O n kvadreret operation.
Ser man på vores pseudokode, har vi også en løkke indlejret i
en anden sløjfe, som faktisk lyder som en O
n kvadreret funktion.
Men husk, at vi ikke behøvede at kigge over
hele listen ved fastsættelsen af ​​mindstebeløbet usorteret element?
Når vi vidste, at 4 blev sorteret, for eksempel, havde vi ikke
nødt til at se på det igen.
Så betyder det lavere køretid?
For vores liste over længde 6, havde vi brug for at lave fem
sammenligninger for det første element, fire sammenligninger for
det andet element, og så videre.
Det betyder, at det samlede antal af trin er summen af
de hele tal fra 1 til længden af ​​listen minus 1.
Vi kan repræsentere dette med en summation.
Vi vil ikke gå ind i summationer her.
Men det viser sig, at denne summation er lig med n gange
n minus 1 over 2.
Eller ækvivalent, n kvadreret over 2 minus n over 2.
Når vi taler om asymptotisk runtime, denne n kvadreret udtryk
vil dominere dette n sigt.
Så selection slags er O n potens.
Husk på, at i vores eksempel, udvælgelse slags stadig behov for
kontrollere, om et nummer, der allerede var sorteret
nødvendig for at blive flyttet.
Så det betyder, at hvis vi kørte udvælgelse slags over en allerede
sorteret liste, ville det kræve det samme antal skridt, da det
ville, når du kører over et helt usorteret liste.
Så selection art har en bedste fald udførelse af n kvadreret,
som vi repræsenterer med omega n potens.
Og det er det for udvælgelse slags.
Blot én af de mange algoritmer, vi kan
bruge til at sortere en liste.
Mit navn er Tommy, og dette er CS50.