Invoegsortering: algoritme met C, C++, Java, Python Voorbeelden

Wat is invoegsortering?

Insertion sort is een van de vergelijkende sorteeralgoritmen die worden gebruikt om elementen te sorteren door op één element tegelijk te itereren en het element op de juiste positie te plaatsen.

Elk element wordt opeenvolgend ingevoegd in een reeds gesorteerde lijst. De grootte van de reeds gesorteerde lijst is aanvankelijk één. Het invoegsorteeralgoritme zorgt ervoor dat de eerste k-elementen worden gesorteerd na de k-de iteratie.

Kenmerken van het invoegsorteeralgoritme

Het algoritme voor invoegsortering heeft de volgende belangrijke kenmerken:

  • Het is een stabiele sorteertechniek, waardoor de relatieve volgorde van gelijke elementen niet verandert.
  • Het is efficiënt voor kleinere datasets, maar niet effectief voor grotere lijsten.
  • Insertion Sort is adaptief, waardoor het totale aantal stappen wordt verminderd als het gedeeltelijk wordt gesorteerd. reeks wordt geleverd als input om het efficiënt te maken.

Hoe wordt ingevoegd Operawerk?

In het Insertion Sort-algoritme wordt de insert-bewerking gebruikt om ongesorteerde elementen te sorteren. Het helpt om een ​​nieuw element in een reeds gesorteerde lijst in te voegen.

Pseudocode van invoegbewerking:

Beschouw een lijst A met N elementen.

A[N-1] is the element to be inserted in the sorted sublist A[0..N-2].
For i = N-1 to 1:
if A[i] < A[i-1], then swap A[i] and A[i-1]
else Stop   

Invoegen Operawerk

In het bovenstaande voorbeeld moet een nieuw element 6 in een reeds gesorteerde lijst worden ingevoegd.

Stap 1) Vergeleken met het links aangrenzende element van A[5], 9 > 6, verwisselen we de positie van 9 en 6. Nu wordt element 6 verplaatst naar A[4].

Stap 2) Nu vergelijken we A[4] en A[3], en we vinden dat A[3] > A[4], we wisselen opnieuw de positie van 6 en 8.

Stap 3) Vergelijk nu A[3] en A[2], aangezien A[2] > A[3] de positie van 7 en 6 verwisselt.

Stap 4) We vergelijken A[1] en A[2], en als A[1] < A[2], dwz het links aangrenzende element is niet langer groter. Nu concluderen we dat 6 correct is ingevoegd en stoppen we het algoritme hier.

Hoe de invoegsortering werkt

De hierboven besproken insert-bewerking is de ruggengraat van de insertion sort. De insert-procedure wordt op elk element uitgevoerd en uiteindelijk krijgen we de gesorteerde lijst.

Invoegsortering werkt

De bovenstaande voorbeeldfiguur demonstreert de werking van invoegsortering in de datastructuur. Aanvankelijk is er slechts één element aanwezig in de gesorteerde sublijst, namelijk 4. Na het invoegen van A[1], oftewel 3, groeit de grootte van de gesorteerde sublijst naar 2.

C++ Programma voor invoegsortering

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
    
    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]); 

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){        
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    return 0;
}

Output:

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

C-code voor invoegsortering

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Output:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Programma voor invoegsortering

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Output:

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Eigenschappen van invoegsortering

Hier zijn belangrijke eigenschappen van invoegsortering:

  • online: Invoegsortering kan elementen sorteren zoals deze worden ontvangen. Dat wil zeggen, als we al een lijst met elementen hebben gesorteerd en nog wat elementen aan de lijsten hebben toegevoegd, hoeven we de hele sorteerprocedure niet opnieuw uit te voeren. In plaats daarvan hoeven we alleen maar te herhalen op nieuw toegevoegde elementen.
  • In situ: De ruimtecomplexiteit van het insertion sort-algoritme is constant en vereist geen extra ruimte. Dit algoritme sorteert elementen op hun plaats.
  • Stal: Bij invoegsortering wisselen we de elementen niet om als hun waarden gelijk zijn. Twee elementen, x en y, zijn bijvoorbeeld gelijk, en x verschijnt vóór y in ongesorteerde lijsten, terwijl in de gesorteerde lijst x vóór y verschijnt. Dit maakt de invoegsoort stabiel.
  • Aangepaste: A sorteeralgoritme is adaptief als het minder tijd kost als de invoerelementen of subset van elementen al gesorteerd zijn. Zoals we hierboven hebben besproken, is de beste looptijd van insertion sort O(N), en de slechtste looptijd O(N^2). Insertion sort is een van de adaptieve sorteeralgoritmen.

Complexiteit van invoegsortering

Complexiteit van de ruimte

Voor het invoegsorteren is geen extra ruimte nodig om de elementen te sorteren; de ruimtecomplexiteit is constant, d.w.z. O(1).

Tijdcomplexiteit

Omdat insertion sort elk element gelijktijdig itereert, zijn er N-1 passes nodig om N elementen te sorteren. Voor elke pass kan het nul swaps maken als de elementen al gesorteerd zijn, of swap als de elementen in aflopende volgorde zijn gerangschikt.

  • Voor pas 1 zijn de minimaal vereiste swaps nul en de maximaal vereiste swaps 1.
  • Voor pas 2 zijn de minimaal vereiste swaps nul en de maximaal vereiste swaps 2.
  • Voor pass N is de minimaal vereiste swap nul en de maximaal vereiste swaps N.
  • De minimale swap is nul, dus de beste tijdcomplexiteit is O(N) voor het herhalen van N passes.
  • Het totale maximale aantal swaps is (1+2+3+4+..+N) i. N(N+1)/2, de slechtste tijdscomplexiteit is O(N^2).

Hier is de belangrijke tijdcomplexiteit van insertion sort:

  • Ergste geval complexiteit: O(n2): Een array in aflopende volgorde sorteren als deze in oplopende volgorde staat, is het worstcasescenario.
  • Beste geval complexiteit: O(n): Best Case Complexity treedt op wanneer de array al is gesorteerd, de outer loop n keer wordt uitgevoerd terwijl de inner loop helemaal niet wordt uitgevoerd. Er zijn slechts n aantal vergelijkingen. Dus in dit geval is de complexiteit lineair.
  • Gemiddelde casuscomplexiteit: O(n2): Het gebeurt wanneer de elementen van een array voorkomen in de door elkaar gegooide volgorde, die noch oplopend noch aflopend is.

Samenvatting

  • Invoegsortering is een sorteeralgoritmemethode die is gebaseerd op de vergelijking.
  • Het is een stabiele sorteertechniek, waardoor de relatieve volgorde van gelijke elementen niet verandert.
  • Bij elk element wordt de invoegbewerking gebruikt om het element in de gesorteerde sublijst in te voegen.
  • Invoegsortering is een in-place sorteeralgoritme.
  • De slechtste en gemiddelde tijdcomplexiteit van insertion sort is kwadratisch, d.w.z. O(N^2).
  • Bij invoegsortering is geen extra ruimte nodig.