[MUSIC SPILLE] 

DOUG LLOYD: Så innsetting sort er en annen algoritme vi kan bruke til å sortere en matrise. Ideen bak denne algoritmen er å bygge din sorterte utvalg på plass, forskyvning av elementene den måten som du går, for å gjøre plass. Dette er litt annerledes fra utvalget sort eller boble slag, for eksempel, der vi justere steder, hvor vi gjør bytteavtaler. 

I dette tilfellet hva vi faktisk gjør er glideelementer over, ut av veien. Hvordan virker denne algoritmen arbeide i pseudokode? Vel la oss bare vilkårlig si at første element i matrisen er sortert. Vi bygger den på plass. 

Vi skal gå ett element om gangen og bygge den, og så det første vi ser er et element av en matrise. Og per definisjon, en en element tabellen er sortert. 

Så får vi gjenta denne prosessen until-- vi vil gjenta følgende prosess inntil alle elementene er sortert. Se på den neste usortert element og sett det inn i den sorterte delen, ved å forskyve det nødvendige antall av elementer ut av veien. Forhåpentligvis kan dette visualisering vil hjelpe deg å se nøyaktig hva som er skjer med innsetting slag. 

Så igjen, her er vår Hele usortert array, alle de elementer som er angitt i rødt. Og la oss følge trinnene ved pseudokode. Det første vi gjør, er vi kaller første element i matrisen, sortert. Så vi er bare skal si five, du er nå sortert. 

Deretter ser vi på neste usortert element i matrisen og vi ønsker å sette inn som inn i den sorterte del, ved å flytte elementene over. Så to er neste usortert element i matrisen. Klart det hører før fem, så hva vi skal gjøre er liksom holde to til side for en andre, skifte five over, og deretter sett i to før fem, hvor du skal gå. Og nå kan vi si at to er sortert. 

Så som du kan se, har vi bare så langt sett på to elementer av matrisen. Vi har ikke sett på hvile i det hele tatt, men vi har fikk disse to elementene sortert etter hjelp av skiftemekanismen. 

Så vi gjenta prosessen på nytt. Se på den neste usortert element, er at en. La oss holde det til side for en andre, skifte alt over, og sette en hvor den skal gå. 

Igjen, fortsatt, har vi bare noen gang så på en, to og fem. Vi vet ikke hva annet som kommer, men vi har sortert disse tre elementene. 

Neste usortert element er tre, så vi får sett den til side. Vi skal skifte over hva vi må, som denne gang er ikke alt som i forrige to tilfeller er det bare fem. Og så får vi holde oss tre i, mellom to og fem. 

Seks er neste usortert element til matrisen. Og i virkeligheten seks er større enn fem, så vi trenger ikke engang å gjøre noe bytte. Vi kan bare tack seks rett på å enden av sortert partiet. 

Endelig er fire den siste usortert element. Så vi får sett den til side, skifte over elementene vi trenger å skifte over, og deretter sette fire der det hører hjemme. Og nå ser, har vi liksom av alle elementene. Legg merke til med innsetting sortere, har vi ikke å gå frem og tilbake over rekken. Vi bare gikk over rekken en gang, og vi flyttet ting at vi allerede hadde oppstått, for å gjøre plass til de nye elementene. 

Så hva er det verste tilfellet scenario med innsetting slag? I verste tilfelle, matrise er i omvendt rekkefølge. Man må skifte hvert av de n elementene opp til n stillinger, hver eneste gang vi gjøre en innsetting. Det er mye giring. 

I beste tilfelle er matrise er perfekt sortert. Og liksom som hva som skjedde med fem og seks i eksemplet der vi kunne bare tråkle den på uten å måtte gjøre noe skiftende, vi skulle egentlig gjøre det. 

Hvis du forestille deg at vår matrise var én til seks, Vi vil starte med å erklære en er sortert. To kommer etter en slik at vi kan bare sier, OK, vel en og to er sortert. Tre kommer etter to så, OK, en og to og tre er sortert. 

Vi er ikke å gjøre noen bytteavtaler, vi er bare å flytte denne vilkårlig linje mellom sortert og usortert mens vi går. Så effektivt som vi gjorde i eksempelet, snu elementer blå, så vi fortsetter. Så hva er den verste fall runtime, da? Husk, hvis vi må skifte hver av de n elementene muligens n posisjoner, forhåpentligvis som gir deg en idé om at det verste tilfellet runtime er Big O n squared. 

Hvis rekken er helt sortert, alt vi har å gjøre er å se på hvert enkelt element en gang, og så er vi ferdige. Så i beste fall, det er omega n. 

Jeg er Doug Lloyd. Dette er CS50.