[MUSIC SPILLE] DOUG LLOYD: Utvalg sort er en algoritme som, som du kanskje forventer, sorterer et sett av elementer. Og algoritme tilbakekalling er en steg-for-steg sett instruks for å fullføre en oppgave. 

I utvalget sortere grunnleggende ideen er dette, finne den minste usortert element og legge den til slutten av den sorterte listen. Effektivt hva dette gjør er build en sortert liste, ett element om gangen. Bryte det ned til pseudo vi kunne oppgi denne algoritmen som følger, gjenta dette til ingen usorterte elementer forbli. Gjennom usortert søke data for å finne den minste verdien, deretter bytte den minste verdien med første element i usortert del. 

Det kan bidra til å visualisere dette, så la oss ta en titt på dette. Så dette, jeg hevder, er en usortert array og jeg har indikeres det ved å indikerer at all av elementene er farget rød, de er ennå ikke sortert. Dette er hele usortert del av tabellen. 

Så la oss gå gjennom trinnene utvalg sorter å sortere array. Så igjen, vi skal gjenta til det gjenstår noen usorterte elementer. Vi skal søke gjennom data for å finne den minste verdien, og deretter bytte denne verdien med første element i usortert del. 

Akkurat nå, igjen, hele matrise er usortert del. Alle de røde elementene er usortert. Så vi søke gjennom og vi finner den minste verdien. Vi starter i begynnelsen, vi går til enden, vi finne den minste verdien er, en. Så det er en del en. Og så del to, bytte denne verdien med det første element av usortert del, eller den første røde element. 

I dette tilfellet ville det være fem, så vi bytte en og fem. Når vi gjør dette, kan vi visuelt se at vi har flyttet den minste verdsatt element av tabellen, til begynnelsen. Effektivt sortering som element. 

Og så kan vi faktisk bekrefte og stat at man blir sortert. Og så får vi indikere sortert delen av vår rekke, ved å farge det blå. 

Nå er vi bare gjenta prosessen på nytt. Vi søker gjennom usortert del av array for å finne den minste element. I dette tilfellet er det to. 

Vi bytter at med det første element i usortert del. I dette tilfellet to også tilfeldigvis det første elementet i usortert del. Så vi bytte to med seg selv, som egentlig bare etterlater to hvor det er, og det er sortert. Fortsetter på, søke vi gjennom for å finne den minste element. Det er tre. Vi bytte den med det første element, som er fem. Og nå tre er sortert. 

Vi søker gjennom igjen, og vi finner det minste elementet er fire. Vi bytte den med det første elementet av usortert del, og nå er det fire er sortert. 

Vi finner at fem er det minste elementet. Vi bytte den med det første element i usortert del. Og nå har fem er sortert. 

Og så til slutt, vår usortert delen består av bare et enkelt element, så vi søker gjennom og vi finner at seks er minste, og faktisk bare element. Og så kan vi si at det er sortert. Og nå har vi slått våre utvalg fra å være helt usortert rødt, å fullstendig, sortert i blått, ved hjelp av valg liksom. 

Så hva er worst case scenario her? Vel i den absolutt verste tilfelle, må vi se over alle elementene i matrisen til finne den minste usortert element, og vi må gjenta denne prosessen n ganger. En gang for hvert element i matrisen fordi bare vi, i denne algoritmen, sort element på en gang. 

Hva er den best case scenario? Vel det er akkurat det samme, ikke sant? Vi har faktisk å fortsatt gå gjennom hvert enkelt element i matrisen for å bekrefte at det er, faktisk det minste elementet. 

Så verste fall runtime, vi må gjenta en prosess n ganger, en gang for hver av n elementer. Og i beste fall vi må gjøre det samme. 

Så tenker tilbake til vår beregningsorientert kompleksitet verktøykasse, hva tror du er den verste case runtime for valg slag? Hva tror du er den beste case runtime for valg slag? 

Visste du gjette Big O n squared, og Big Omega n squared? Du ville være riktig. De er, faktisk, worst case og best case run ganger, for valg liksom. 

Jeg er Doug Lloyd. Dette er CS50.