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