[Musik spiller] 

DOUG LLOYD: Så indsættelse slags er en anden algoritme vi kan bruge til at sortere et array. Ideen bag denne algoritme er at opbygge din sorterede vifte på plads, skiftende elementer ud af den måde, som du går, for at gøre plads. Dette er en smule anderledes fra valg sortere eller boble Sorter, for eksempel, hvor vi justerer de steder, hvor vi laver swaps. 

I dette tilfælde, hvad vi er faktisk gør, er glidende elementer i, ud af vejen. Hvordan denne algoritme arbejde i pseudokode? Jamen lad os bare vilkårligt sige, at første element i arrayet er sorteret. Vi bygger det på plads. 

Vi skal gå ét element ad gangen, og bygge det, og så det første vi ser er en ét element array. Og per definition en en element array sorteret. 

Så vil vi gentage denne proces until-- vi vil gentage følgende proces indtil alle elementer sorteres. Kig på den næste usorterede element og indsætte det i sorterede portion ved at flytte det krævede antal elementer af vejen. Forhåbentlig vil denne visualisering vil hjælpe dig se præcis, hvad der er foregår med indsættelse slags. 

Så igen, her er vores Hele usorteret array, alle elementerne vist med rødt. Og lad os følge den trin i vores pseudokode. Det første, vi gør, er vi kalder første element i arrayet, sorteres. Så vi er bare vil sige fem, er du nu ordnet. 

Så ser vi på den næste usorteret element i arrayet og vi ønsker at indsætte, at i sorteret del, ved at flytte elementer i. Så to er den næste usorteret element i arrayet. Klart det hører inden fem, så hvad vi skal gøre er slags holde to til side til en anden, skift fem forhold, og derefter indsætte to før fem, hvor de skal skal gå. Og nu kan vi sige, at to er sorteret. 

Så som du kan se, har vi kun hidtil så på to elementer i arrayet. Vi har ikke set på hvile på alle, men vi har fik disse to elementer ordnet efter måde skiftemekanismen. 

Så vi gentage processen igen. Kig på den næste usorteret element, det er en. Lad os antage, at afsat til en anden, skift alt forbi, og sætte en hvor det skal gå. 

Igen, stadig, vi har kun nogensinde så på én, to og fem. Vi ved ikke, hvad der ellers er på vej, men vi har ordnet disse tre elementer. 

Næste usorteret element er tre, så vi vil sætte den til side. Vi vil ændre sig med det, vi skal der, denne gang er ikke alt som i den tidligere to tilfælde, det er bare de fem. Og så vil vi holde os tre i, mellem to og fem. 

Seks er den næste usorteret element til arrayet. Og i virkeligheden seks er større end fem, så Vi behøver ikke engang at gøre noget swapping. Vi kan bare tack seks til højre ad slutningen af ​​sorteret del. 

Endelig er fire sidste usorteret element. Så vi vil lægge det til side, skift i løbet af de elementer, vi har brug for at flytte forbi, og derefter sætte fire, hvor den hører. Og nu se, vi har sortering af alle elementerne. Læg mærke med indsættelse sortere, havde vi ikke at gå frem og tilbage over array. Vi gik kun på tværs array én gang, og vi skiftede ting at vi havde allerede stødt på, med henblik på at gøre plads til de nye elementer. 

Så hvad er den værste fald scenarie med indsættelse slags? I værste tilfælde array er i omvendt rækkefølge. Du er nødt til at flytte hvert af n elementer op til n positioner, hver eneste gang vi foretage en indsættelse. Det er en masse skiftende. 

I bedste tilfælde er den array er perfekt sorteret. Og lidt ligesom, hvad der skete med fem og seks i eksempel hvor vi bare kunne hæfte det på uden at skulle gøre noget skiftende, vi ville hovedsageligt gøre. 

Hvis du forestiller dig, at vores matrix var en til seks, vi ville starte med erklære en sorteres. To kommer efter en, så vi kan bare sige, OK, godt et og to er ordnet. Tre kommer efter to så, OK, en og to og tre er ordnet. 

Vi er ikke at foretage nogen swaps, er vi bare flytte denne vilkårlige linje mellem sorteret og usorteret, som vi går. Så effektivt som vi gjorde i eksemplet, dreje elementer blå, som vi går videre. Så hvad er den værste fald runtime, så? Husk, at hvis vi er nødt til at flytte hver af de n elementer eventuelt N positioner, forhåbentlig, der giver dig en idé om, at det værste tilfælde runtime er Big O n potens. 

Hvis array er perfekt sorteret, alt, hvad vi har at gøre er at se på hvert enkelt element én gang, og så vi er færdig. Så i bedste fald, det er omega n. 

Jeg er Doug Lloyd. Det er CS50.