[MUSIK SPELA] 

DOUG LLOYD: Så insättningssortering är en annan algoritm vi kan använda för att sortera en array. Tanken bakom denna algoritm är att bygga din sorterade arrayen på plats, flytta delar av det sätt som du går, för att göra plats. Detta är något annorlunda från val sortera eller bubbla sortera, till exempel, där vi justera platser, där vi gör swappar. 

I detta fall vad vi faktiskt gör är glidelement över, ur vägen. Hur fungerar denna algoritm arbeta i pseudokod? Bra låt oss bara godtyckligt säga att första elementet i arrayen sorteras. Vi bygger den på plats. 

Vi ska gå en del i taget och bygga det, och så det första vi ser är en en elementgrupp. Och per definition, en elementuppsättningen sorteras. 

Sedan ska vi upprepa denna process until-- vi ska upprepa följande process tills alla elementen sorteras. Titta på nästa osorterat elementet och sätt in det i den sorterade delen, genom att skifta det nödvändiga antalet element ur vägen. Förhoppningsvis visualisering hjälper dig att se exakt vad som är händer med insättningssortering. 

Så återigen, här är vår Hela osorterade array, alla element markerade med rött. Och låt oss följa stegen att vår pseudokod. Det första vi gör är vi kallar första elementet i arrayen, sortering. Så vi är bara gonna säga fem, du nu sortering. 

Sedan tittar vi på nästa osorterade element i arrayen och vi vill infoga att in i den sorterade partiet, genom att flytta element över. Så två är nästa osorterade element i gruppen. Tydligt den tillhör före fem, så vad vi ska göra är slags hålla två åt sidan för en andra, skift fem över, och sedan in två före fem, där att ska gå. Och nu kan vi säga att två sorteras. 

Så som ni kan se, vi har bara så långt tittat på två element i arrayen. Vi har inte tittat på vila alls, men vi har fick dessa två element sorterat efter sätt av växlingsmekanismen. 

Så vi upprepar processen igen. Titta på nästa osorterade element, det är en. Låt oss hålla det åt sidan för en sekund, skifta allt över, och sätta en där det ska gå. 

Återigen, fortfarande, vi har bara någonsin tittat på ett, två, och fem. Vi vet inte vad som kommer, men vi har sorterat dessa tre element. 

Nästa osorterat elementet är tre, så vi ska ställa den åt sidan. Vi kommer att flytta över vad vi behöver som, denna gång är inte allt som i föregående två fall är det bara fem. Och sedan ska vi hålla tre, mellan de två och fem. 

Sex är nästa osorterade element till arrayen. Och i själva verket sex är större än fem, så Vi behöver inte ens göra något byte. Vi kan bara tack sex rätt på I slutet av den sorterade delen. 

Slutligen, är fyra av sista osorterade element. Så vi ska ställa den åt sidan, flytta över de element som vi behöver för att flytta över, och sedan lägga fyra där den hör hemma. Och nu ser, vi har sort av alla element. Lägg märke med insättning sortera, hade vi inte att gå fram och tillbaka över matrisen. Vi gick bara över matrisen en tid, och vi skiftade saker att vi hade redan stött på, för att att göra plats för de nya elementen. 

Så vad är det värsta fallet scenario med insättningssortering? I värsta fall, den array är i omvänd ordning. Du måste flytta vart och ett av n element upp till n positioner, varenda gång vi göra en införing. Det är en mycket växling. 

I bästa fall, den array är perfekt sorteras. Och ungefär som vad som hände med fem och sex i exemplet, där vi bara kunde lägga fram det på utan att behöva göra någon växling, Vi skulle i princip göra det. 

Om ni föreställa er att vår matris var en genom sex, vi skulle börja med förklara ett sorteras. Två kommer efter en så att vi kan bara säger, OK, väl ett och två är sorterade. Tre kommer efter två så, OK, en och två och tre sorteras. 

Vi är inte gör några swappar, vi är bara flytta denna godtycklig linje mellan sorteras och osorterade när vi går. Så effektivt som vi gjorde i exemplet, roterande element blå, som vi går vidare. Så vad är det värsta fallet runtime, då? Kom ihåg att om vi måste flytta vart och ett av de n elementen eventuellt N-positionema, förhoppningsvis som ger dig en idé som det värsta fallet runtime är Big O n kvadrat. 

Om arrayen är perfekt sorteras, allt vi har att göra är att titta på varje enskilt element en gång, och sedan vi är klar. Så i bästa fall, är det omega n. 

Jag är Doug Lloyd. Detta är CS50.