In de kern dient insertion sort als een sorteeralgoritme. Het kan verschillende ongesorteerde elementen bij elke iteratie op de voor hen meest geschikte plaats zetten. Je zou kunnen zeggen dat dit algoritme ongeveer hetzelfde werkt als hoe mensen kaarten sorteren in hun handen. Als je ervaring hebt met kaartspelen, weet je dat kaartspelers sorteren in de veronderstelling dat de eerste kaarten al gesorteerd zijn, waarna ze de ongesorteerde kaarten selecteren.
Indien de ongesorteerde kaart groter blijkt te zijn dan de kaart in de hand van de speler, moet hij deze kaart rechts leggen. Anders moeten ze de kaart aan de linkerkant houden. Op dezelfde manier moet je de rest van de ongesorteerde kaarten plaatsen en op hun respectievelijke plaats houden. De aanpak van insertion sort lijkt hier sterk op.
De basisprincipes van hoe sorteren door invoeging werkt
Hieronder vindt u drie stappen die u een overzicht geven van de manier waarop insertion sort werkt:
- In de eerste stap worden de elementen in kwestie vergeleken met de elementen die ernaast liggen
- Als uit elke vergelijking blijkt dat het element in kwestie op een bepaalde positie kan worden gebruikt, dan wordt er ruimte voor gemaakt. Dit wordt gedaan door de positie van andere elementen naar rechts te verschuiven.
- Deze procedure gaat door tot elk element in de array zijn juiste plaats heeft gevonden
Kenmerken van Insertion Sort
Hoewel dit in-place sorteeralgoritme een breed scala aan kenmerken heeft, zijn er drie belangrijke waarmee iedereen vertrouwd moet raken.
- Ten eerste is het insertion sort algoritme ongelooflijk eenvoudig. Sommigen zouden zelfs zeggen dat het het eenvoudigste algoritme is dat er is, vanwege de eenvoudige implementatie
- Als u een programmeur bent die regelmatig te maken heeft met kleine gegevenswaarden, zal het gebruik van dit algoritme u goed van pas komen
- De aard van het insertion sort algoritme is vrij adaptief, waardoor het ideaal is voor gedeeltelijk gesorteerde gegevensverzamelingen
Veel gestelde vragen over Insertion Sort
Hier is een lijst met beknopte antwoorden op veelgestelde vragen over de insertion sort-algoritmen.
Wat zijn grensgevallen van het insertion sort-algoritme?
Insertion sort vergt veel tijd als het gaat om het sorteren van elementen die in omgekeerde volgorde staan. Als de elementen echter al gesorteerd zijn, zal het niet veel tijd kosten.
Zijn Insertion Sort-algoritmen stabiel?
Insertion sort algoritmen zijn ongelooflijk stabiel, vooral als u ze vergelijkt met andere algoritmen.
Wanneer is de beste tijd om het Insertion Sort algoritme te gebruiken?
Zoals eerder vermeld, wordt Insertion Sort vaak gebruikt als er een klein aantal elementen is. Het kan echter ook heel handig zijn als een invoerarray niet al te veel sortering nodig heeft en slechts een paar misplaatste elementen bevat.
Welke benadering volgt Insertion Sort?
De aanpak die wordt gevolgd door het insertion sort-algoritme is incrementeel, en daarom is het ongelooflijk populair onder programmeurs die arrays sorteren.
Binair invoegsorteren uitgelegd
Programmeurs kunnen binair zoeken gebruiken om het aantal vergelijkingen in gewone insertion sort te verminderen. Binary insertion sort maakt gebruik van zoeken voor het vinden van de ideale plaats voor het invoegen van het gekozen item bij elke iteratie. Bij gewoon invoegen gebruikt het sorteren in het ergste geval O(i) (bij de i-de iteratie).
We kunnen binair onderzoek gebruiken om dit te reduceren tot: O(logi). Dit gezegd zijnde, heeft het algoritme echter nog steeds een looptijd rond O(n^2) voor worst cases. Dit is te wijten aan het aantal swaps dat nodig is per insertie.
Stappen voor het implementeren van Insertion Sort in gelinkte lijsten
De onderstaande stappen laten zien hoe men gebruik kan maken van het insertion sort algoritme in een gekoppelde lijst.
- Begin met het maken van een gesorteerde lijst en zorg ervoor dat deze leeg is
- Doorloop de gemaakte lijst en volg deze stap voor elk knooppunt
- Voer het huidige knooppunt in de vorm van resultaat of gesorteerde lijst in
- Verander tenslotte het hoofd van de gelinkte lijst, waardoor het hoofd van de gesorteerde lijst wordt, ook wel resultaatlijst genoemd
De belangrijkste toepassingen van Insertion Sort
Hier zijn twee van de meest voorkomende scenario’s wanneer programmeurs insertion sort gebruiken.
– Ten eerste gebruiken ze het wanneer er een array is met een paar elementen
– Insertion sort kan ook van pas komen als er slechts een klein aantal elementen te sorteren is.
Tijdscomplexiteit van insertion sort
Hier is een blik op de tijdcomplexiteit die je kunt tegenkomen bij insertion sort.
Worst case complexiteit O (n2) – Worst Case Complexity O (n2)
Stel je voor dat er een array in oplopende volgorde aanwezig is, die je in aflopende volgorde wilt sorteren. Een dergelijk geval resulteert in worst-case complexiteit. In zo’n situatie moet je elk element vergelijken met andere elementen, zodat er (n-1) vergelijkingen zijn voor elk n-de element.
Het totale aantal vergelijkingen zal n*(n-1) ~ n2 zijn
Gemiddelde complexiteit O(n) – Average Case Complexity O(n)
Dit type complexiteit treedt vaak op wanneer de elementen van een array door elkaar gehusseld zijn, wat betekent dat ze noch in aflopende, noch in oplopende volgorde staan.
Ruimte-complexiteit – Space Complexity
De ruimte-complexiteit wordt 0(1) wanneer er een extra variabele wordt geïmplementeerd.
Best case complexiteit – Best Case Complexity
Wanneer een array geen sortering behoeft, is het aantal keren dat de buitenste lus draait n. Anderzijds blijft de binnenste lus inactief en doet geen loop. Dit betekent dat het aantal vergelijkingen n zal zijn, wat resulteert in een lineaire complexiteit.
Analyse van de tijdcomplexiteit
Het valt niet te ontkennen hoe efficiënt insertion sort is, maar als men een array die al gesorteerd is, aan insertion sort zou geven, zal het algoritme nog steeds de andere voor de lus uitvoeren. Dit zal n stappen vergen voor het sorteren van een array van de n elementen die om te beginnen al gesorteerd waren, waardoor de tijdcomplexiteit in het beste geval in een lineaire n-functie verandert.
Een ongesorteerde array heeft een element nodig voor het maken van vergelijkingen met andere elementen, wat betekent dat elk element van n wordt vergeleken met andere n elementen. Het zou ook helpen om andere soortgelijke algoritmen zoals Quick Sort, Merge Sort of Selection Sort te analyseren en hun respectieve complexiteit te meten.
