insertion sort c with examples
Een diepgaande blik op invoegsortering met klassieke voorbeelden.
Invoegsortering is een sorteertechniek die kan worden bekeken op een manier waarop we kaarten uit de hand spelen. De manier waarop we een kaart in een stapel plaatsen of verwijderen, werkt sorteren op een vergelijkbare manier.
De algoritmetechniek voor invoegsortering is efficiënter dan de technieken voor het sorteren van bellen en selectie, maar is minder efficiënt dan de andere technieken zoals Quicksort en sortering samenvoegen.
Bekijk hier de beste C ++ trainingshandleidingen.
Wat je leert:
- Overzicht
- Algemeen algoritme
- Pseudocode
- Illustratie
- C ++ Voorbeeld
- Java-voorbeeld
- Complexiteitsanalyse van het invoegsorteeralgoritme
- Gevolgtrekking
- Aanbevolen literatuur
Overzicht
Bij de invoegsorteertechniek gaan we uit van het tweede element en vergelijken het met het eerste element en plaatsen het op de juiste plaats. Vervolgens voeren we dit proces uit voor de volgende elementen.
We vergelijken elk element met al zijn voorgaande elementen en plaatsen of plaatsen het element op de juiste plaats. Invoegsorteertechniek is beter haalbaar voor arrays met een kleiner aantal elementen. Het is ook handig voor het sorteren van gekoppelde lijsten.
wat is de beste computerreiniger
Gelinkte lijsten hebben een pointer naar het volgende element (in het geval van een enkelvoudig gelinkte lijst) en ook een pointer naar het vorige element (in het geval van een dubbel gelinkte lijst). Daarom wordt het eenvoudiger om invoegsortering voor een gekoppelde lijst te implementeren.
Laten we in deze tutorial alles over invoegsortering onderzoeken.
Algemeen algoritme
Stap 1 : Herhaal stap 2 t / m 5 voor K = 1 t / m N-1
Stap 2 : set temp = A (K)
Stap 3 : stel J = K - 1 in
Stap 4 : Herhaal terwijl temp<=A(J)
set A (J + 1) = A (J)
stel J = J - 1
(einde van binnenste lus)
Stap 5 : set A (J + 1) = temp
(einde van lus)
Stap 6 : Uitgang
Bij de invoegsorteertechniek gaan we dus uit van het tweede element, aangezien we aannemen dat het eerste element altijd gesorteerd is. Vervolgens vergelijken we van het tweede element tot het laatste element elk element met al zijn voorgaande elementen en zetten dat element op de juiste positie.
Pseudocode
De pseudocode voor invoegsortering wordt hieronder gegeven.
Hierboven is de pseudocode voor invoegsortering gegeven. Vervolgens zullen we deze techniek in het volgende voorbeeld illustreren.
Illustratie
De te sorteren array is als volgt:
Nu vergelijken we voor elke doorgang het huidige element met al zijn voorgaande elementen. Dus in de eerste doorgang beginnen we met het tweede element.
We hebben dus een N aantal passages nodig om een array met N aantal elementen volledig te sorteren.
De bovenstaande illustratie kan in tabelvorm worden samengevat:
| Slagen voor | Ongesorteerde lijst | vergelijking | Gesorteerde lijst |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12.3} | {3,12,5,10,8,1} |
| twee | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| 3 | {3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | | | {1,3,5,8,10,12} |
Zoals te zien is in de bovenstaande illustratie, beginnen we met de 2ndelement aangezien we aannemen dat het eerste element altijd gesorteerd is. We beginnen dus met het vergelijken van het tweede element met het eerste en wisselen van positie als het tweede element kleiner is dan het eerste.
Dit vergelijkings- en ruilproces plaatst twee elementen op de juiste plaats. Vervolgens vergelijken we het derde element met zijn vorige (eerste en tweede) elementen en voeren we dezelfde procedure uit om het derde element op de juiste plaats te plaatsen.
Op deze manier plaatsen we voor elke doorgang één element op zijn plaats. Voor de eerste doorgang plaatsen we het tweede element op zijn plaats. Om N-elementen op hun juiste plaats te plaatsen, hebben we dus in het algemeen N-1-passen nodig.
Vervolgens zullen we de implementatie van de invoegsorteertechniek in C ++ - taal demonstreren.
C ++ Voorbeeld
Uitgang:
Invoerlijst is
12 4 3 1 15 45 33 21 10 2
Gesorteerde lijst is
1 2 3 4 10 12 15 21 33 45
website die youtube-video's omzet naar mp4
Vervolgens zullen we de Java-implementatie van de invoegsorteertechniek zien.
Java-voorbeeld
Uitgang:
Invoerlijst met elementen ...
12 4 3 1 15 45 33 21 10 2
gesorteerde lijst met elementen ...
1 2 3 4 10 12 15 21 33 45
In beide implementaties kunnen we zien dat we beginnen met sorteren vanaf de 2ndelement van de array (lusvariabele j = 1) en vergelijk herhaaldelijk het huidige element met al zijn voorgaande elementen en sorteer het element om het op de juiste positie te plaatsen als het huidige element niet in orde is met al zijn voorgaande elementen.
Invoegsortering werkt het beste en kan in minder passages worden voltooid als de array gedeeltelijk is gesorteerd. Maar naarmate de lijst groter wordt, nemen de prestaties af. Een ander voordeel van invoegsortering is dat het een stabiele sortering is, wat betekent dat de volgorde van gelijke elementen in de lijst behouden blijft.
Complexiteitsanalyse van het invoegsorteeralgoritme
Uit de pseudocode en de bovenstaande illustratie is invoegsortering het efficiënte algoritme in vergelijking met bellen- of selectiesortering. In plaats van for-lus- en present-voorwaarden te gebruiken, gebruikt het een while-lus die geen extra stappen meer uitvoert wanneer de array wordt gesorteerd.
wat is traceerbaarheidsmatrix bij het testen van software
Maar zelfs als we de gesorteerde array doorgeven aan de invoeging-sorteertechniek, zal het nog steeds de buitenste for-lus uitvoeren, waardoor n aantal stappen nodig is om een reeds gesorteerde array te sorteren. Dit maakt de beste tijdcomplexiteit van invoegsortering een lineaire functie van N, waarbij N het aantal elementen in de array is.
De verschillende complexiteiten voor de invoegsorteertechniek worden hieronder gegeven:
| Tijdscomplexiteit in het ergste geval | O (n 2) |
| Tijdscomplexiteit in het beste geval | Aan) |
| Gemiddelde tijdcomplexiteit | O (n 2) |
| Complexiteit van de ruimte | O (1) |
Ondanks deze complexiteit kunnen we toch concluderen dat invoegsortering het meest efficiënte algoritme is in vergelijking met de andere sorteertechnieken zoals Bubble sort en Selection sort.
Gevolgtrekking
Invoegsortering is de meest efficiënte van alle drie tot dusver besproken technieken. Hier gaan we ervan uit dat het eerste element is gesorteerd en vervolgens herhaaldelijk elk element met al zijn voorgaande elementen vergelijken en vervolgens het huidige element op de juiste positie in de array plaatsen.
In deze tutorial hebben we bij het bespreken van invoegsortering opgemerkt dat we de elementen vergelijken met een toename van 1 en dat ze ook aaneengesloten zijn. Deze functie heeft tot gevolg dat er meer passen nodig zijn om de gesorteerde lijst te krijgen.
In onze aanstaande tutorial zullen we 'Shell sorteren' bespreken, wat een verbetering is ten opzichte van de selectie sortering.
In shell-sortering introduceren we een variabele die bekend staat als 'increment' of een 'gap', waarmee we de lijst verdelen in sublijsten met niet-aaneengesloten elementen die 'gap' uit elkaar staan. Shell-sortering vereist minder passages in vergelijking met invoegsortering en is ook sneller.
In onze toekomstige tutorials zullen we leren over twee sorteertechnieken, “Quicksort” en “Mergesort” die de “Verdeel en heers” -strategie gebruiken voor het sorteren van datalijsten.
Bekijk hier de Beginners C ++ Trainingsgids.
Aanbevolen literatuur
- Shell-sortering in C ++ met voorbeelden
- Selectie sorteren in C ++ met voorbeelden
- MongoDB Sort () -methode met voorbeelden
- Unix-sorteeropdracht met syntaxis, opties en voorbeelden
- Bubbelsortering in C ++ met voorbeelden
- Heap-sortering in C ++ met voorbeelden
- Sorteer samenvoegen in C ++ met voorbeelden
- Snel sorteren in C ++ met voorbeelden