[Powered by Google Translate] [Insertion Sorter]
[Tommy MacWilliam] [Harvard University]
[Dette er CS50.TV]
La oss ta en titt på innsetting sortere, en algoritme for å ta en liste med tall og sortere dem.
En algoritme, husk, det er rett og slett en steg-for-trinn prosedyre for å oppnå en oppgave.
Den grunnleggende ideen bak innsetting sortere, er å dele vår liste i to deler,
en sortert del og en usortert del.
>> På hvert trinn av algoritmen, er et nummer flyttes
fra usorterte porsjon til den sorterte parti
til slutt hele listen sorteres.
Her er listen over seks usorterte tall - 23, 42, 4, 16, 8, og 15.
Siden disse tallene er ikke alle i stigende rekkefølge, de unsorted.
Siden vi ikke har begynt å sortere ennå, vil vi vurdere alle seks elementene vår usortert del.
>> Når vi begynner å sortere, vil vi sette disse sortert tallene til venstre for disse.
Så, la oss starte med 23, det første elementet i listen vår.
Vi har ikke noen elementer i vår sortert del ennå,
så la oss rett og slett vurdere 23 for å være starten og slutten av vår sortert del.
Nå har vår sortert delen ett nummer, 23,
og vår usortert del har disse fem tall.
La oss nå sette inn neste nummer i vår usortert del, 42, inn i sorteres del.
>> For å gjøre dette, må vi sammenligne den 42 til 23 - det eneste elementet i vår sortert del så langt.
Førtito er større enn 23, så vi kan bare legge 42 til slutten
av kildesortert parti av listen. Flott!
Nå kan våre sorteres del har to elementer, og vår usortert del har fire elementer.
Så, la oss nå flytte til 4, det neste elementet i usortert del.
Så, bør der dette plasseres i den sorterte del?
>> Husk, vi ønsker å plassere dette nummeret i sortert rekkefølge
så vår sortert del forblir riktig sortert til alle tider.
Hvis vi plasserer 4 til høyre for 42, så vår liste vil være ute av drift.
Så, la oss fortsette å flytte høyre mot venstre i våre slags del.
Når vi beveger oss, la oss skifte hvert nummer ned et sted å gjøre plass til det nye nummeret.
Ok, er 4 også mindre enn 23, så vi kan ikke plassere det her heller.
La oss flytte 23 rette sted.
>> Det betyr at vi ønsker å plassere 4 inn det første sporet i den sorterte delen.
Legg merke til hvordan denne plassen på listen var allerede tom,
fordi vi har vært på vei sortert elementer ned som vi har møtt dem.
OK. Så, vi halvveis.
La oss videre vår algoritme ved å sette 16 inn den sorterte parti.
Seksten er mindre enn 42, så la oss forskyve 42 til høyre.
Seksten er også mindre enn 23, så la oss også skifte det elementet.
>> Nå er 16 større enn 4. Så det ser ut som vi ønsker å sette inn 16 mellom 4 og 23.
Mens flytte gjennom den sorterte parti av listen fra høyre mot venstre,
4 er det første tallet vi har sett som er mindre enn antallet
vi prøver å sette inn.
Så nå kan vi sette inn 16 i denne tomme sporet,
som, husk, vi har laget av bevegelige elementer i den slags del over
som vi har møtt dem.
>> OK. Nå har vi fire sortert elementer og to usorterte elementer.
Så, la oss flytte åtte i den sorterte delen.
Åtte er mindre enn 42.
Åtte er mindre enn 23.
Og 8 er mindre enn 16 år.
Men 8 er større enn 4.
Så vil vi gjerne sette åtte mellom 4 og 16 år.
Og nå er det bare ett element til venstre for å sortere - den 15.
Femten er mindre enn 42,
Femten er mindre enn 23.
Og 15 er mindre enn 16.
Men 15 er større enn 8.
>> Så, her er der vi ønsker å gjøre vårt endelige innsetting.
Og vi er ferdige.
Vi har ingen flere elementer i usortert del,
og vår sortert delen er i riktig rekkefølge.
Tallene er bestilt fra minste til største.
Så, la oss ta en titt på noen pseudokode som beskriver hvilke tiltak vi bare utført.
>> På linje 1, kan vi se at vi må iterere over hvert element i listen
bortsett fra den første, vil siden det første elementet i usortert del rett og slett blitt
det første elementet i den sorterte delen.
På linjene 2 og 3, vi holde styr på vår nåværende plass i usortert del.
Element representerer nummeret vi nå beveger seg inn i sortert del,
og j representerer vår indeksen inn i usortert del.
>> På linje 4, vi gjentar gjennom den sorterte delen fra høyre til venstre.
Vi ønsker å stoppe iterating når elementet til venstre for vår nåværende posisjon
er mindre enn elementet vi prøver å sette inn.
På linje 5, vi flytter hvert element vi møter en plass til høyre.
På den måten vil vi ha en klar plass til å sette inn når vi finner det første elementet
mindre enn elementet vi flytte.
På linje 6, vi oppdaterer vår mot å fortsette å bevege seg mot venstre gjennom den sorterte delen.
Endelig, på linje 7, vi setter elementet inn i sorterte parti av listen.
>> Vi vet at det er greit å sette på plass j,
fordi vi allerede har flyttet element som pleide å være der en plass til høyre.
Husk, vi beveger seg gjennom den sorterte delen fra høyre til venstre,
men vi skal flytte gjennom usortert del fra venstre til høyre.
OK. La oss nå ta en titt på hvor lenge kjører som algoritmen tok.
Vi vil først stille spørsmålet hvor lang tid tar det for denne algoritmen til å kjøre i verste fall.
Husker at vi representerer dette gangtid med Big O notasjon.
For å sortere vår liste, vi måtte iterere over elementene i usortert del,
og for hver av disse elementer, potensielt over alle elementer i den sorterte del.
Intuitivt, dette høres ut som en O (n ^ 2) drift.
>> Ser på pseudokode vår, har vi en løkke nestet inni en annen loop,
som riktignok høres ut som en O (n ^ 2) drift.
Men gjorde den sorterte delen av listen ikke inneholder hele listen helt til slutten.
Likevel kunne vi potensielt sette et nytt element på begynnelsen av kildesortert del
på hver iterasjon av algoritmen,
noe som betyr at vi måtte se på hvert element for tiden i den sorterte delen.
Slik, betyr at vi kan potensielt gjøre en sammenligning for det andre elementet,
to sammenligninger for det tredje elementet, og så videre.
Så, er det totale antall trinn summen av de hele tall fra 1 til lengden av listen minus 1.
Vi kan representere dette med en summering.
>> Vi vil ikke gå inn summeringer her, men det viser seg at dette summering er lik
n (n - 1) i løpet 2, som er ekvivalent n ^ 2/2 - N / 2.
Når man snakker om asymptotisk kjøretid,
dette n ^ 2 sikt kommer til å dominere denne n sikt.
Så, er innsetting slags Big O (n ^ 2).
Hva om vi kjørte innsetting sortere på en allerede sortert liste.
I så fall, ville vi bare bygge opp den sorterte delen fra venstre til høyre.
Så vil vi bare trenger i størrelsesorden n trinn.
>> Det betyr at innsetting sorter har en beste fall ytelse av n,
som vi representerer med Ω (n).
Og det er det for innsetting sortere,
bare ett av mange algoritmer vi kan bruke til å sortere en liste.
Mitt navn er Tommy, og dette er CS50.
[CS50.TV]
Å, du bare ikke kan stoppe det når det begynner.
Oh, vi gjorde det - >> Boom!