[Powered by Google Translate] [Infogning Sortera] [Tommy MacWilliam] [Harvard University] [Detta är CS50.TV] Låt oss ta en titt på insättning sortera, en algoritm för att ta en lista med tal och sortera dem. En algoritm, kom ihåg, är helt enkelt ett steg-för-steg förfarande för att utföra en uppgift. Den grundläggande idén bakom införandet sortera, är att dela vår lista i två delar, en sorterad del och en osorterad parti. 

Vid varje steg i algoritmen, är ett antal flyttas från osorterade delen till den sorterade delen tills slutligen hela listan är sorterad. Här är listan över sex osorterade tal - 23, 42, 4, 16, 8, och 15. Eftersom dessa siffror är inte alla i stigande ordning, de är osorterade. Eftersom vi inte har börjat sortera ännu, vi betrakta alla sex element vårt osorterat del. 

När vi börjar sortera, vi sätta dessa sorterade siffror till vänster om dessa. Så, låt oss börja med 23, det första elementet i vår lista. Vi har inte några element i vår sorterade del ännu, så låt oss bara betrakta 23 som början och slutet av vår sorterade delen. Nu har vår sorterade delen en siffra, 23, och vår osorterade delen har dessa fem siffror. Låt oss nu in i nästa nummer i vår osorterat del, 42, in i den sorterade delen. 

För att göra det behöver vi för att jämföra 42 till 23 - den enda del i vår sorterade delen hittills. Fyrtiotvå är större än 23, så vi kan helt enkelt lägga 42 till slutet av den sorterade delen av listan. Bra! Nu har vår sorterade del har två element, och vår osorterade del har fyra delar. Så, låt oss nu gå till 4, nästa element i osorterade delen. Så bör där detta placeras i den sorterade delen? 

Kom ihåg, vill vi placera detta nummer i sorterad ordning så vår sorterade partiet förblir korrekt sorteras vid alla tidpunkter. Om vi ​​placerar 4 till höger om 42, så vår lista kommer att vara ur funktion. Så, låt oss fortsätta gå höger till vänster i vår Sortera del. När vi går, låt oss flytta varje nummer ned en plats att göra plats för det nya numret. Okej, är 4 också mindre än 23, så vi kan inte placera den här heller. Låt oss flytta 23 rätta ställe. 

Det betyder att vi vill placera 4 i den första öppningen i sorterade delen. Lägg märke till hur detta utrymme i listan redan tom, eftersom vi har rört sig sorterade element ner som vi har stött dem. Okej. Så, vi halvvägs där. Låt oss fortsätta vår algoritm genom att föra in 16 i den sorterade delen. Sexton är mindre än 42, så låt oss flytta 42 till höger. Sexton är också mindre än 23, så låt oss också flytta det elementet. 

Nu är 16 större än 4. Så ser det ut som om vi skulle vilja sätta in 16 mellan 4 och 23. När du flyttar genom den sorterade delen av listan från höger till vänster, 4 är det första numret har vi sett som är mindre än det antal vi försöker infoga. Så nu kan vi sätta in 16 i denna tomma plats, som kom ihåg, har vi skapat av rörliga element i sorteringen delen över som vi har stött på dem. 

Okej. Nu har vi fyra sorterade element och två osorterade element. Så, låt oss flytta 8 i den sorterade delen. Åtta är mindre än 42. Åtta är mindre än 23. Och 8 är mindre än 16. Men 8 är större än 4. Så vill vi att sätta in 8 mellan 4 och 16. Och nu har vi bara en del kvar att sortera - den 15. Femton är mindre än 42, Femton är mindre än 23. Och 15 är mindre än 16. Men 15 är större än 8. 

Så, här är där vi vill göra vår sista insättning. Och vi är klara. Vi har inga fler element i osorterade delen, och vår sorterade delen är i rätt ordning. Siffrorna är ordnade från lägsta till högsta. Så, låt oss ta en titt på några pseudokod som beskriver de steg vi bara utförs. 

På rad 1, kan vi se att vi kommer att behöva iterera över varje element i listan utom den första, kommer sedan den första delen i den osorterade delen helt enkelt bli det första elementet i den sorterade delen. På linje 2 och 3, vi hålla koll på vår nuvarande plats i osorterade delen. Element representerar antalet vi nu går in i den sorterade delen, och j representerar vårt index i osorterade delen. 

På rad 4, vi iterera igenom den sorterade delen från höger till vänster. Vi vill sluta iteration när elementet till vänster om vår nuvarande position är mindre än elementet vi försöker infoga. På rad 5, vi flytta varje element vi möter ett utrymme till höger. På så sätt kommer vi att ha ett fritt utrymme för att infoga i när vi hittar det första elementet mindre än elementet vi flyttar. På rad 6, vi uppdaterar vår disk för att fortsätta att röra sig kvar genom den sorterade delen. Slutligen, på linje 7, vi sätter elementet i den sorterade delen av listan. 

Vi vet att det är okej att sätta på plats j, eftersom vi har redan flyttat det element som används för att vara där en plats till höger. Kom ihåg, vi rör sig genom den sorterade delen från höger till vänster, men vi rör sig genom osorterade delen från vänster till höger. Okej. Låt oss nu ta en titt på hur långvariga som algoritm tog. Vi kommer först fråga frågan hur lång tid tar det för denna algoritm att köra i värsta fall. Minns att vi representerar det gångtid med Big O notation. För att sortera vår lista, vi var tvungna att iterera över elementen i osorterade delen, och för varje enskild beståndsdel, eventuellt över alla element i den sorterade delen. Intuitivt, detta låter som en O (n ^ 2) drift. 

Titta på vår pseudokod har vi en slinga kapslad inuti en annan slinga, som faktiskt låter som en O (n ^ 2) drift. Däremot har den sorterade delen av listan innehåller inte hela listan ända till slutet. Ändå kan vi sätta potentiellt nytt element i början av sorterade delen på varje iteration av algoritmen, vilket innebär att vi skulle behöva titta på varje element närvarande i den sorterade delen. Så innebär att vi skulle kunna göra en jämförelse för det andra elementet, två jämförelser för det tredje elementet, och så vidare. Så är det totala antalet steg summan av heltalen från 1 till längden av listan minus 1. Vi kan representera detta med en summering. 

Vi kommer inte att gå in i summeringar här, men det visar sig att denna summering är lika med n (n - 1) över 2, vilket motsvarar n ^ 2/2 - N / 2. När man talar om asymptotisk runtime, Detta n ^ 2 term kommer att dominera denna N sikt. Så, införande Sortera Big O (n ^ 2). Tänk om vi körde insättning Sortera på en redan sorterad lista. I så fall skulle vi bygga helt enkelt upp den sorterade delen från vänster till höger. Så behöver vi bara på beställning av n steg. 

Det innebär att införandet Sortera har bästa fall prestanda N, som vi representerar med Ω (n). Och det är det för insättning sortera, bara en av de många algoritmer som vi kan använda för att sortera en lista. Mitt namn är Tommy, och detta är CS50. [CS50.TV] Åh, du bara inte kan sluta att när det börjar. Åh, vi gjorde det - >> Boom!