[Powered by Google Translate] [Indsættelse Sorter] [Tommy MacWilliam] [Harvard University] [Dette er CS50.TV] Lad os tage et kig på indsættelse slags, en algoritme til at tage en liste over numre og sortere dem. En algoritme, husk, er simpelthen en trin-for-trin procedure for opstilling af en opgave. Den grundlæggende idé bag indsættelse slags, er at opdele vores liste i to dele, en sorteret del og en usorteret portion. 

På hvert trin af algoritmen er en række flyttet fra usorteret del til den sorterede portion indtil sidst hele listen er sorteret. Her er listen af ​​seks usorterede numre - 23, 42, 4, 16, 8 og 15. Da disse tal ikke er alle i stigende rækkefølge, de er usorteret. Da vi ikke er begyndt sortering endnu, vil vi overveje alle seks elementer vores usorteret portion. 

Når vi begynder sortering, vil vi sætte disse sorteret numre til venstre for disse. Så lad os starte med 23, det første element i vores liste. Vi har ikke nogen elementer i vores sorteret del endnu, så lad os blot overveje 23 være begyndelsen og slutningen af ​​vores sorteret portion. Nu er vores sorteret del har ét nummer, 23, og vores usorteret del har disse fem numre. Lad os nu indsætte det næste nummer i vores usorterede portion, 42, ind i den sorterede del. 

For at gøre dette, vil vi nødt til at sammenligne den 42 til 23 - det eneste element i vores sorterede portion hidtil. Fyrre-to er større end 23, så vi kan blot tilføje 42 til enden Den sorterede portion af listen. Great! Nu er vores sorteres del har to elementer, og vores usorteret del har fire elementer. Så lad os nu gå videre til 4, det næste element i den usorterede del. Så bør hvor det placeres i den sorterede portion? 

Husk, vi ønsker at placere dette nummer i sorteret orden så vores sorteret del forbliver korrekt sorteret på alle tidspunkter. Hvis vi placerer 4 til højre for 42, så vores liste vil være ude af drift. Så lad os fortsætte med at bevæge højre mod venstre i vores slags portion. Som vi bevæger os, lad os flytte hvert nummer ned et sted at gøre plads til det nye nummer. Okay, 4 er også mindre end 23, så vi kan ikke placere den her heller. Lad os flytte den 23 rigtige sted. 

Det betyder, at vi gerne vil placere 4 i den første slot i den sorterede del. Bemærk hvordan denne plads på listen allerede var tom, fordi vi har været i bevægelse sorteret elementer ned som vi har mødt dem. Ok. Så vi er halvvejs. Lad os fortsætte vores algoritme ved at sætte 16 ind i sorterede portion. Seksten er mindre end 42, så lad os flytte 42 til højre. Seksten er også mindre end 23, så lad os også skifte dette element. 

Nu, 16 er større end fire. Så det ser ud som vi gerne vil indsætte 16 mellem 4 og 23. Samtidig bevæger sig gennem sorteret del af listen fra højre mod venstre, 4 er det første tal, vi har set, at der er mindre end det antal, vi forsøger at indsætte. Så nu kan vi indsætte de 16 i denne tomme slot, der, husk, har vi skabt ved at flytte elementer i den slags del over som vi har mødt dem. 

Ok. Nu har vi fire sorteret elementer og to usorterede elementer. Så lad os flytte 8 i den sorterede del. Otte er mindre end 42. Otte er under 23. Og 8 er mindre end 16. Men 8 er større end 4. Så vil vi gerne indsætte 8 mellem 4 og 16. Og nu har vi bare have én mere tilbage element til at sortere - de 15. Femten er mindre end 42, Femten er under 23. Og 15 er mindre end 16. Men 15 er større end 8. 

Så her er, hvor vi ønsker at gøre vores endelige indsættelse. Og vi er færdige. Vi har ikke flere elementer i den usorterede del, og vores sorteres del er i den rigtige rækkefølge. Numrene bestilles fra den mindste til den største. Så lad os tage et kig på nogle pseudokode, der beskriver de skridt, vi har lige udført. 

På linie 1, kan vi se, at vi bliver nødt til at gentage over hvert element i listen undtagelse af den første, vil siden det første element i den usorterede del simpelthen blive det første element i den sorterede del. På linjer 2 og 3, vi holde styr på vores nuværende plads i usorterede del. Element repræsenterer antallet vi i øjeblikket bevæger sig ind i den sorterede portion, og j repræsenterer vores indeks i usorteret portion. 

På linje 4, vi iteration gennem den sorterede del fra højre mod venstre. Vi ønsker at holde op med iteration, når elementet til venstre for vores nuværende position er mindre end det element, vi forsøger at indsætte. I linje 5, vi flytte hvert element møder vi en plads til højre. På den måde, vil vi have en klar plads til at indsætte ind i, når vi finder det første element mindre end det element, vi flytter. I linje 6, opdaterer vi vores tæller fortsat at flytte til venstre gennem den sorterede del. Endelig, på linje 7, vi isætningen af ​​elementet i den sorterede del af listen. 

Vi ved, at det er ok at indsætte i position j, fordi vi allerede har flyttet det element, der bruges til at være der en plads til højre. Husk, vi bevæger sig gennem den sorterede del fra højre til venstre, men vi flytter gennem den usorterede del fra venstre til højre. Ok. Lad os nu tage et kig på, hvor lang tid kørende, algoritme tog. Vi vil først spørge, hvor lang tid tager det for denne algoritme til at køre i værste fald. Husk på, at vi repræsenterer dette køretid med Big O notation. For at sortere vores liste, vi havde til at gentage over elementerne i den usorterede del, og for hver af disse bestanddele, eventuelt over alle elementer i den sorterede portion. Intuitivt dette lyder som en O (n ^ 2) operation. 

Ser man på vores pseudokode, har vi en løkke indlejret i en anden sløjfe, som, ja, lyder som en O (n ^ 2) operation. Men den sorterede del af listen ikke indeholder hele listen, indtil den bitre ende. Alligevel kunne vi potentielt indsætte et nyt element i begyndelsen af ​​det sorterede portion på hver iteration af algoritmen, hvilket betyder, at vi er nødt til at se på hvert element i øjeblikket i den sorterede del. Så det betyder, at vi potentielt kunne gøre en sammenligning for det andet element, to sammenligninger for det tredje element, og så videre. Så er det samlede antal af trin er summen af ​​de hele tal fra 1 til længden af ​​listen minus 1. Vi kan repræsentere dette med en summation. 

Vi vil ikke gå ind i summationer her, men det viser sig, at denne summation er lig med n (n - 1) over 2, hvilket er ækvivalent n ^ 2/2 - n / 2. Når vi taler om asymptotisk runtime, denne n ^ 2 udtryk kommer til at dominere denne n sigt. Så indsættelse slags er Big O (n ^ 2). Hvad hvis vi løb indsættelse slags på en allerede sorteret liste. I dette tilfælde ville vi blot opbygge det sorterede portion fra venstre mod højre. Så vi behøver kun i størrelsesordenen n trin. 

Det betyder, at insertion art har en bedst tænkelige ydeevne n, som vi repræsenterer med Ω (n). Og det er det for indsættelse slags, blot én af de mange algoritmer, vi kan bruge til at sortere en liste. Mit navn er Tommy, og dette er CS50. [CS50.TV] Åh, du kan bare ikke stoppe, at når den starter. Åh, vi gjorde det - >> Boom!