[Muziek] 

DOUG LLOYD: Dus insertion sort is een ander algoritme we kunnen gebruiken om een ​​array te sorteren. Het idee achter dit algoritme is het gesorteerde array bouwen in de plaats, het verschuiven van elementen uit de weg als je gaat, om ruimte te maken. Dit is iets anders uit selectie sort of bel sorteren, bijvoorbeeld wanneer we het aanpassen van de locaties, waar we het maken van swaps. 

In dit geval wat we eigenlijk doen is schuifelementen over, uit de weg. Hoe werkt dit algoritme werken in pseudocode? Nou laten we gewoon willekeurig zeggen dat de eerste element van de array wordt gesorteerd. We bouwen op zijn plaats. 

We gaan één element in een tijd en bouwen, en dus het eerste wat we zien is één element array. En per definitie een element-array wordt gesorteerd. 

Dan zullen we dit proces herhalen until-- zullen we het volgende proces te herhalen totdat alle elementen gesorteerd. Kijk naar de volgende ongesorteerd element en voeg deze aan de gesorteerde gedeelte, door het verschuiven van het vereiste aantal elementen uit de weg. Hopelijk deze visualisatie helpt u precies zien wat er er met insertion sort. 

Dus nogmaals, hier is onze hele ongesorteerde array, alle elementen in rood aangegeven. En laten we volgen stappen pseudocode. Het eerste wat we doen, we noemen het eerste element van de array gesorteerd. Dus we gaan gewoon zeg vijf, je bent nu opgelost. 

Daarna kijken we naar de volgende ongesorteerde element van de array en we willen voegen dat in de gesorteerde gedeelte, door het verschuiven van elementen over. Dus twee is de volgende ongesorteerd element van de array. Het is duidelijk dat het voor het hoort vijf, dus wat we gaan doen is een soort van houden twee opzij voor een tweede, verschuiven vijf over, en plaats twee voor vijf, waar je moet gaan. En nu kunnen we zeggen dat twee wordt gesorteerd. 

Dus zoals je kunt zien, hebben we alleen zo ver bekeek twee elementen van de array. We hebben niet gekeken naar de rust helemaal niet, maar we hebben kreeg deze twee elementen naargelang weg van het schakelmechanisme. 

Zodat we het proces herhalen. Kijk naar de volgende ongesorteerde element, dat is één. Laten we stellen dat gereserveerd voor een tweede, verschuiven alles over, en zet een waar het zou moeten gaan. 

Nogmaals, nog steeds, hebben we alleen ooit keken, twee en vijf. We weten niet wat er nog komt, maar we hebben deze drie elementen gesorteerd worden. 

Volgende ongesorteerd element drie, dus we zullen het opzij zetten. We zullen verschuiven over wat we moeten die ditmaal niet alles zoals in het voorgaande twee gevallen, het is gewoon de vijf. En dan zullen we drie in steken, tussen de twee en vijf. 

Zes is de volgende ongesorteerd element aan de array. En inderdaad zes meer dan vijf, dus we niet eens behoefte aan een swapping doen. We kunnen gewoon overstag zes recht op het einde van de gesorteerde gedeelte. 

Tenslotte vier de laatste ongesorteerd element. Dus we het opzij zetten, dan verschuiven de elementen moeten we dan verschuiven, en vervolgens vier waar het thuishoort. En kijk nu, we hebben een soort alle elementen. Opmerken met invoeging sorteren, hebben we niet heen en weer over de matrix gaan. We gingen alleen over de array één keer, en we verschoven dingen dat we al hadden ondervonden, met het oog om ruimte voor de nieuwe elementen te maken. 

Dus wat is het ergste geval scenario met inbrengen soort? In het ergste geval, de array in omgekeerde volgorde. Je moet elk van de n elementen verschuiven tot n posities, iedere keer dat wij maak een inbrengen. Dat is een hoop van het verschuiven. 

In het beste geval is de array wordt perfect opgelost. En een soort als wat er gebeurd met vijf en zes in het voorbeeld, waar we konden gewoon overstag het op zonder enige verschuiving te doen, we zouden in wezen dat te doen. 

Als je je voorstellen dat onze serie was één tot en met zes, we af zou beginnen door verklaren één wordt gesorteerd. Twee komt na een, zodat we kunnen gewoon zeggen, OK, goed één en twee zijn gesorteerd. Drie komt na twee zo, OK, één en twee en drie zijn gesorteerd. 

We zijn niet het maken van een swap, we zijn gewoon verplaatsen van dit willekeurige lijn tussen gesorteerd en ongesorteerd als we verder gaan. Zo effectief we in het voorbeeld, draaien elementen blauw, als we verder gaan. Dus wat is het ergste geval runtime, dan? Vergeet niet, als we moeten elke shift de n elementen eventueel n plaatsen, hopelijk dat geeft een idee dat het ergste geval runtime is Big O n kwadraat. 

Als de matrix perfect naargelang, alles wat we moeten doen is te kijken naar elk element een keer, en dan zijn we klaar. Dus in het beste geval is het omega van de n. 

Ik ben Doug Lloyd. Dit is CS50.