[Powered by Google Translate] [Invoeging Sorteren] [Tommy MacWilliam] [Harvard University] [Dit is CS50.TV] Laten we eens een kijkje nemen op insertion sort, een algoritme voor het nemen van een lijst van nummers en ze te sorteren. Een algoritme onthouden is gewoon een stap-voor-stap procedure voor het bereiken van een taak. Het basisidee achter insertion sort, is om onze lijst te verdelen in twee delen, een gesorteerd deel en een ongesorteerd deel. 

Bij elke stap van het algoritme wordt een aantal bewogen van het ongesorteerde deel naar het gedeelte gesorteerd totdat uiteindelijk de gehele lijst is gesorteerd. Hier is de lijst van zes ongesorteerde getallen - 23, 42, 4, 16, 8 en 15. Aangezien deze nummers zijn niet allemaal in oplopende volgorde, ze gesorteerd. Aangezien wij nog niet begonnen sorteren nog, zullen we rekening houden met alle zes elementen onze ongesorteerde deel. 

Zodra we beginnen met het sorteren, zullen we deze gesorteerd getallen aan de linkerkant van deze. Dus, laten we beginnen met 23, het eerste element in onze lijst. Wij hebben nog geen elementen in ons gesorteerd gedeelte, dus laten we gewoon 23 overwegen om het begin en het einde van onze gesorteerd deel zijn. Nu, onze gesorteerd deel heeft een nummer, 23, en onze ongesorteerde deel heeft deze vijf nummers. Laten we nu het volgende nummer in te voegen in onze ongesorteerd deel, 42, in de gesorteerde gedeelte. 

Om dit te doen, zullen we moeten de 42 te vergelijken met de 23 - het enige element in onze gesorteerd deel tot nu toe. Tweeënveertig groter is dan 23, dus we kunnen alleen maar 42 toevoegen aan het einde van de gesorteerde deel van de lijst. Geweldig! Nu onze gesorteerd gedeelte bestaat uit twee elementen, en onze ongesorteerde deel heeft vier elementen. Dus, laten we nu naar de 4, het volgende element in de ongesorteerde deel. Ja, waar deze worden geplaatst in de gesorteerde gedeelte? 

Vergeet niet, we willen dit aantal plaatsen in gesorteerde volgorde zodat onze gesorteerd gedeelte blijft correct gesorteerd te allen tijde. Als we de vier aan de rechterkant van de 42, dan is onze lijst zal worden van de orde. Dus, laten we verder naar rechts te verplaatsen naar links in onze sorteren gedeelte. Als we bewegen, laten we elk nummer terug te schakelen een plek om ruimte te maken voor het nieuwe nummer. Oke, 4 is ook minder dan 23, dus we kunnen niet hier plaatsen het ook niet. We gaan de 23 juiste plaats. 

Dat betekent dat we graag de 4 plaatsen in de eerste sleuf in de gesorteerde gedeelte. Merk op hoe deze ruimte in de lijst al leeg was, omdat we al bewegende gesorteerd elementen zijn als we ooit ontmoet ze. Oke. Dus, we zijn halverwege. Laten we ons algoritme voort te zetten door het plaatsen van de 16 in de gesorteerde gedeelte. Zestien is minder dan 42, dus laten we de 42 naar rechts. Zestien is ook minder dan 23, dus laten we ook dat element verschuiven. 

Nu 16 is groter dan 4. Dus, het lijkt erop dat we graag de 16 in te voegen tussen de 4 en de 23. Terwijl u de gesorteerde deel van de lijst van rechts naar links, 4 is het eerste nummer die we hebben gezien dat kleiner is dan het aantal we proberen in te voegen. Zo, nu kunnen we invoegen de 16 in deze lege sleuf, die vergeet niet, hebben we gecreëerd door bewegende elementen in het soort gedeelte boven zoals we hebben ondervonden ze. 

Oke. Nu, hebben we vier gesorteerd elementen en twee ongesorteerde elementen. Dus, laten we de 8 te verplaatsen naar de gesorteerde gedeelte. Acht is minder dan 42. Acht is minder dan 23. En 8 kleiner is dan 16. Slechts 8 hoger is dan 4. Dus, willen we graag de 8 in te voegen tussen de 4 en de 16. En nu hebben we alleen nog een verlaten meer elementen te sorteren - de 15. Vijftien is minder dan 42, Vijftien is minder dan 23. En 15 is minder dan 16. Maar 15 groter is dan 8. 

Dus, hier is waar we willen onze laatste inbrengen te maken. En we zijn klaar. We hebben geen elementen in de ongesorteerde gedeelte, en ons gesorteerd gedeelte in de juiste volgorde. De nummers zijn gerangschikt volgens de van klein naar groot. Dus, laten we een kijkje nemen op een aantal pseudocode dat de stappen die we zojuist uitgevoerde beschrijft. 

Op lijn 1, kunnen we zien dat we moeten itereren over elk element in de lijst behalve de eerste, zal omdat het eerste element in de ongesorteerde gedeelte eenvoudigweg het eerste element in de gesorteerde gedeelte. Op lijnen 2 en 3, zijn we het bijhouden van onze huidige plaats in het ongesorteerde deel. Element staat voor het aantal die we momenteel verhuizen naar de gesorteerde gedeelte, en j vertegenwoordigt onze index in de ongesorteerde deel. 

Op lijn 4, we itereren door het gesorteerd gedeelte van rechts naar links. Gestopt moet itereren wanneer de element links van de huidige positie is minder dan het element dat we proberen in te voegen. Op lijn 5, we verschuiven elk element dat we een ruimte tegenkomen naar rechts. Op die manier zullen we een duidelijke ruimte om in te voegen in wanneer we het eerste element minder dan het element dat we gaan verhuizen. Op lijn 6, we updaten onze balie te blijven bewegen naar links door de gesorteerde gedeelte. Tot slot, op lijn 7, we plaatsen het element in de gesorteerde deel van de lijst. 

We weten dat het goed is om in te voegen in de juiste positie j, omdat we al verplaatst het element dat wordt gebruikt om daar te zijn een plaats naar rechts. Vergeet niet, we bewegen door de gesorteerde gedeelte van rechts naar links, maar we gaan door het ongesorteerde deel van links naar rechts. Oke. Laten we nu eens kijken hoe lang loopt dat algoritme hebben deelgenomen. We zullen eerst de vraag stellen hoe lang duurt het voor dit algoritme om te draaien in het slechtste geval. Herinner je dat we deze looptijd vertegenwoordigen met Big O notatie. Om onze lijst te sorteren, moesten we itereren over de elementen in het ongesorteerde deel, en voor elk van deze elementen mogelijk over alle elementen in de gesorteerde gedeelte. Intuïtief, dit klinkt als een O (n ^ 2) werking. 

Kijkend naar onze pseudocode, hebben we een lus genest in een andere lus, die inderdaad klinkt als een O (n ^ 2) werking. Echter, de gesorteerde deel van de lijst bevatten niet de hele lijst tot het einde. Toch kunnen we potentieel te voegen een nieuw element aan het begin van de gesorteerde gedeelte elke iteratie van de algoritme, wat betekent dat we zouden hebben om op dit moment te kijken naar elk element in de gesorteerde gedeelte. Dus, dat betekent dat we kunnen potentieel een vergelijking te maken voor het tweede element, twee vergelijkingen voor de derde element, enzovoort. Dus het aantal stappen is de som van de getallen van 1 tot de lengte van de lijst minus 1. We kunnen vertegenwoordigen dit met een sommatie. 

We zullen hier niet ingaan op optellingen, maar het blijkt dat deze opsomming is gelijk aan n (n - 1) over 2, wat overeenkomt n ^ 2/2 - n / 2. Wanneer we spreken over asymptotische runtime, deze n ^ 2 term gaat dit n termijn domineren. Dus, insertion sort is Big O (n ^ 2). Wat als we insertion sort liep op een reeds gesorteerde lijst. In dat geval zou bouwen we eenvoudigweg de gesorteerde gedeelte van links naar rechts. Dus, zullen we alleen maar in de orde van n stappen. 

Dat betekent dat insertion sort een best-case performance van n heeft, die wij vertegenwoordigen met Ω (n). En dat is het voor insertion sort, slechts een van de vele algoritmen die we kunnen gebruiken om een ​​lijst te sorteren. Mijn naam is Tommy, en dit is CS50. [CS50.TV] Oh, je kan het gewoon niet stoppen, dat zodra het begint. Oh, wij deden dat - >> Boom!