[Musik spiller] DOUG LLOYD: valg Sorter er en algoritme, der, som man kunne forvente, sorterer et sæt af elementer. Og algoritme tilbagekaldelse er en trin-for-trin sæt af instruktioner til at fuldføre en opgave. 

I udvælgelsen sortere grundlæggende idé er det, finde den mindste usorteret element og føje den til slutningen af ​​den sorterede liste. Effektivt, hvad det betyder er build en sorteret liste, et element ad gangen. Bryde det ned til pseudokode vi kunne anføre denne algoritme som følger, gentag dette indtil ingen usorterede elementer tilbage. Søg gennem usorterede data for at finde den mindste værdi, derefter bytte den mindste værdi med den første del af usorteret del. 

Det kan hjælpe til at visualisere denne, så lad os tage et kig på dette. Så dette, jeg hævder, er en usorteret array og jeg har angivet, at den ved at angive, at alle af elementerne er farvet rødt, de ikke allerede er sorteret. Dette er hele usorteret del af array'et. 

Så lad os gå gennem trinene valg Sorter for at sortere dette array. Så igen, vi skal gentage indtil der ikke usorterede elementer tilbage. Vi skal søge gennem data for at finde den mindste værdi, og derefter bytte denne værdi med første del af usorteret del. 

Lige nu, igen, at hele array er den usorterede del. Alle de røde elementer er usorteret. Så vi søge gennem og vi finder den mindste værdi. Vi starter i begyndelsen, vi gå til slutningen, vi finder den mindste værdi, en. Så det er første del. Og så del to, bytte denne værdi med det første element i den usorterede del, eller det første røde element. 

I dette tilfælde ville det være fem, så vi bytte et og fem. Når vi gør det, vi kan visuelt se, at vi har flyttede mindste værdsat element af array, til begyndelsen. Effektivt sortering dette element. 

Og så kan vi faktisk bekræfte og præcisere, at én, sorteres. Og så vil vi angive den sorteres del vores array, ved at farve det blå. 

Nu skal vi bare gentage processen igen. Vi søger gennem usorterede del af array for at finde det mindste element. I dette tilfælde er det to. 

Vi bytter at med den første element i usorteret del. I dette tilfælde to også sker for at være det første element af usorteret del. Så vi bytte to med sig selv, som virkelig bare efterlader to hvor det er, og det er sorteret. Fortsætter på, søge vi gennem at finde det mindste element. Det er tre. Vi bytter det med den første element, som er fem. Og nu tre sorteres. 

Vi søge gennem igen, og vi finde det mindste element er fire. Vi bytter det med det første element i den usorteret side og nu fire sorteres. 

Vi finder, at fem er det mindste element. Vi bytter det med den første element i usorteret del. Og nu fem sorteres. 

Og derefter endelig vores usorteret del består af blot et enkelt element, så vi søge gennem og vi finder, at seks er mindste, og i virkeligheden, eneste element. Og så kan vi konstatere, at det er sorteret. Og nu har vi skiftet vores matrix fra at være helt usorterede i rødt, helt sorteres i blå, ved hjælp af udvælgelse slags. 

Så hvad er den værst tænkelige scenarie her? Godt i absolut værste tilfælde har vi at kigge over alle elementerne i arrayet til finde den mindste usorterede element, og vi er nødt til at gentage denne proces n gange. Én gang for hvert element i arrayet fordi kun vi, i denne algoritme, Sorter ét element ad gangen. 

Hvad er den bedste tænkelige scenarie? Jamen det er præcis det samme, ikke? Vi har faktisk stadig gå gennem hvert enkelt element af arrayet med henblik på at bekræfte, at det er, faktisk det mindste element. 

Så værste fald runtime, vi nødt til at gentage en proces n gange, en gang for hver af n elementer. Og i bedste fald, vi er nødt til at gøre det samme. 

Så tænker tilbage til vores beregningsmæssige kompleksitet værktøjskasse, hvad tror du er den værste tilfælde runtime til valg Sorter? Hvad tror du er den bedste tilfælde runtime til valg Sorter? 

Vidste du gætte Big O n kvadreret, og Big Omega n kvadreret? Du ville have ret. Det er, i virkeligheden, værste fald og bedste fald køre gange, for udvælgelse slags. 

Jeg er Doug Lloyd. Det er CS50.