[MUSIK SPELA] DOUG LLOYD: Urval sort är en algoritm som, som man kan förvänta sig, sorterar en rad faktorer. Och algoritm återkallande är ett steg-för-steg set instruktioner för att fylla en uppgift. 

I val sortera Grundidén är detta, hitta minsta osorterat elementet och lägga till det i slutet av den sorterade listan. Effektivt vad detta innebär är build en sorterad lista, ett element åt gången. Bryta ner det till pseudokod Vi kunde konstatera denna algoritm enligt följande, upprepa detta tills inga osorterade element kvar. Söka igenom osorterade data för att hitta det minsta värdet, sedan byta det minsta värdet med första delen av osorterade delen. 

Det kan hjälpa att visualisera detta, så låt oss ta en titt på detta. Så det här, jag hävdar, är en osorterade array och jag har indikeras det genom att ange att alla av elementen är färgade rött, de ännu inte sorteras. Detta är hela osorterat del av matrisen. 

Så låt oss gå igenom stegen val Sortera för att sortera arrayen. Så återigen, vi ska upprepa tills inga osorterade element kvar. Vi ska söka igenom den data för att hitta det minsta värdet, och sedan byta detta värde med första delen av osorterade delen. 

Just nu, återigen, hela array är den osorterade delen. Alla de röda elementen är osorterade. Så vi söker igenom och Vi hittar det lägsta värdet. Vi börjar från början, vi gå till slutet, finner vi det minsta värdet är, en. Så det är en del ett. Och då en del två, byta detta värde med den första delen av den osorterade delen, eller den första röda elementet. 

I detta fall som skulle vara fem, så vi byter en och fem. När vi gör detta, vi kan visuellt se att vi har flyttade minsta värderade elementet av arrayen, till allra första början. Effektivt sortera det elementet. 

Och så vi kan verkligen bekräfta och påstår att man, sorteras. Och så ska vi ange den sorterade delen av vårt utbud, genom att färga det blått. 

Nu har vi bara upprepa processen igen. Vi söka igenom osorterade delen av uppsättningen för att hitta det minsta elementet. I det här fallet är det två. 

Vi byter att med den första del av osorterade delen. I det här fallet två också råkar vara den första delen av den osorterade delen. Så vi byta två med sig själv, som egentligen bara lämnar två där det är, och det är för sortering. Fortsätter vi söka igenom att hitta det minsta elementet. Det är tre. Vi byter den med den första element, vilket är fem. Och nu tre sorteras. 

Vi söker igenom igen, och vi hitta det minsta elementet är fyra. Vi byta det med det första elementet i osorterat del, och nu fyra sorteras. 

Vi finner att fem är det minsta elementet. Vi byter den med den första del av osorterade delen. Och nu fem sorteras. 

Och sedan slutligen, vår osorterade delen består på bara ett enda element, så vi söka igenom och vi tycker att sex är minsta, och i själva verket bara element. Och då kan vi konstatera att den sorteras. Och nu har vi bytte vår array från att vara helt osorterade i rött, helt sorteras i blått, med hjälp av val slag. 

Så vad är det värsta scenariot här? Väl i absolut värsta fallet, måste vi se över alla element i uppsättningen till hitta minsta osorterat elementet, och vi måste upprepa denna process n gånger. En gång för varje element i gruppen eftersom vi bara, i denna algoritm, sortera ett element vid tidpunkten. 

Vad är det bästa scenariot? Jo det är exakt samma, eller hur? Vi har faktiskt fortfarande gå igenom varje enskilt element i matrisen för att bekräfta att det är, i själva verket, det minsta elementet. 

Så värsta fall runtime, vi måste upprepa en process n gånger, en gång för var och en av n element. Och i bästa fall, Vi måste göra detsamma. 

Så tänker tillbaka till vår beräkningskomplexitet verktygslåda, vad tror du är det värsta fall runtime för val sort? Vad tycker du är det bästa fall runtime för val sort? 

Har du gissa Big O n kvadrat, och Big Omega n kvadrat? Du skulle bli rätt. De är i själva verket värsta fall och bästa fall kör tider, för val sort. 

Jag är Doug Lloyd. Detta är CS50.