Invoegsorteeralgoritme met C, C++, Java, Python Voorbeelden

Wat is invoegsortering?

Invoegsorteeralgoritmen (Insertion Sort) zijn een van de vergelijkingssorteeralgoritmen die worden gebruikt om elementen te sorteren door één element tegelijk te doorlopen en het element op de juiste positie binnen een reeds geordend gebied te plaatsen.

Elk element wordt achtereenvolgens ingevoegd in een reeds gesorteerde lijst. De grootte van de reeds gesorteerde lijst is aanvankelijk één. Het Insertion Sort-algoritme zorgt ervoor dat de eerste k elementen gesorteerd zijn na de k-de iteratie van de buitenste lus.

Omdat Insertion Sort het resultaat stapsgewijs opbouwt, is het intuïtief aan te leren, gemakkelijk te debuggen en een sterke basis voor zeer kleine invoerwaarden, waar complexere algoritmen extra overhead zouden veroorzaken zonder meetbare voordelen.

Kenmerken van het invoegsorteeralgoritme

Het algoritme voor Insertion Sort heeft de volgende belangrijke kenmerken die het gedrag ervan bij daadwerkelijke workloads verklaren:

• 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 waar kwadratische groei overheerst.
• Invoegsorteeralgoritme is adaptief, wat betekent dat het totale aantal stappen wordt verminderd als de invoer gedeeltelijk gesorteerd is. reeks wordt als invoer aangeleverd om het efficiënt te maken, omdat willekeurige toegang constante-tijdverschuivingen mogelijk maakt tijdens de binnenste lus.
• Het is een in-place algoritme, dus er is geen extra geheugen nodig dat evenredig is aan de grootte van de invoer.

Met deze eigenschappen in gedachten, wordt in het volgende gedeelte de kernbewerking voor het invoegen van gegevens uitgelegd, die aan de basis ligt van elke iteratie van het algoritme.

Hoe wordt ingevoegd Operawerk?

Bij het invoegsorteeralgoritme wordt de invoegbewerking gebruikt om ongesorteerde elementen te sorteren. Het helpt om een ​​nieuw element in een reeds gesorteerde lijst in te voegen, terwijl de bestaande volgorde van het gesorteerde gedeelte behouden blijft.

Pseudocode van de invoegbewerking:

Beschouw een lijst A met N elementen.

// Insert A[N-1] into 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

In het bovenstaande voorbeeld wordt een nieuw element 6 ingevoegd in een reeds gesorteerde lijst. De volgende stappen trace de binnenste lus terwijl het nieuwe element naar links migreert, richting de juiste positie.

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], dus we wisselen de posities van 6 en 8 weer om.

Stap 3) Vergelijk nu A[3] en A[2]. Omdat A[2] > A[3], wisselen we de posities van 7 en 6 om.

Stap 4) We vergelijken A[1] en A[2]. Omdat A[1] < A[2], is het links aangrenzende element niet langer groter. We concluderen dat 6 correct is ingevoegd en we stoppen de binnenste lus hier.

Hoe de invoegsortering werkt

De hierboven beschreven invoegbewerking vormt de ruggengraat van Insertion Sort. De invoegprocedure wordt uitgevoerd op elk element, en uiteindelijk verkrijgen we de gesorteerde lijst doordat het gesorteerde gebied bij elke buitenste doorgang met één element groeit.

De bovenstaande afbeelding illustreert de werking van Insertion Sort in een datastructuur. Aanvankelijk bevat de gesorteerde sublijst slechts één element, namelijk 4. Na het invoegen van A[1], oftewel 3, groeit de grootte van de gesorteerde sublijst naar 2, en het algoritme zet dit patroon voort totdat elk element is geplaatst.

Nu de conceptuele structuur is vastgesteld, laten de volgende secties concrete implementaties zien in C++, C, en Python Zo kun je lusstructuren in verschillende programmeertalen vergelijken.

C++ Programma voor invoegsortering

De C++ De onderstaande implementatie maakt gebruik van twee geneste lussen: de buitenste lus selecteert het volgende ongesorteerde element, en de binnenste lus verschuift dit naar links totdat de juiste positie is gevonden.

#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

Diezelfde logica is direct toepasbaar op C. De standaard printf De aanroepen vervangen de streamuitvoer, maar het verwisselingspatroon binnen de binnenste lus is identiek aan dat van de C++ versie.

#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

Python ondersteunt tuple swapping in één enkele uitdrukking, waardoor de binnenste lus compacter is dan zijn C en C++ tegenhangers met behoud van hetzelfde algoritmische gedrag.

#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

Hieronder vindt u belangrijke eigenschappen van Insertion Sort die u helpen bepalen wanneer dit de juiste tool is:

• online: Bij invoegsortering worden elementen gesorteerd zodra ze binnenkomen. Als een lijst al gesorteerd is en er vervolgens nieuwe elementen aan worden toegevoegd, hoeven we de hele sorteerprocedure niet opnieuw uit te voeren. In plaats daarvan doorlopen we alleen de nieuw toegevoegde elementen.
• In situ: De ruimtecomplexiteit van het Insertion Sort-algoritme is constant en vereist geen extra geheugen. Dit algoritme sorteert elementen op hun plaats.
• Stal: Bij invoegsortering worden elementen niet verwisseld als hun waarden gelijk zijn. Als twee elementen, x en y, bijvoorbeeld gelijk zijn en x vóór y staat in de ongesorteerde lijst, dan zal x in de gesorteerde lijst nog steeds vóór y staan. Dit maakt invoegsortering stabiel.
• Aangepaste: A sorteeralgoritme Een sorteeralgoritme is adaptief als het minder tijd kost wanneer de invoerelementen of een subset van elementen al gesorteerd zijn. Zoals hierboven besproken, is de beste looptijd van Insertion Sort O(N) en de slechtste looptijd O(N²). Insertion Sort is een van de adaptieve sorteeralgoritmen.

Complexiteit van invoegsortering

De complexiteitsbespreking hieronder behandelt zowel het geheugengebruik als de looptijd, zodat u Insertion Sort kunt vergelijken met alternatieven zoals... Bubble Sorteren en Snel sorteren.

Complexiteit van de ruimte

Insertion Sort vereist geen extra geheugenruimte om de elementen te sorteren. De ruimtecomplexiteit is constant, oftewel O(1), omdat er slechts een paar tijdelijke variabelen worden gebruikt, ongeacht de grootte van de invoer.

Tijdcomplexiteit

Omdat Insertion Sort één element per keer verwerkt, zijn er N-1 passes nodig om N elementen te sorteren. Bij elke pass kunnen er nul wisselingen plaatsvinden als de elementen al gesorteerd zijn, of er kunnen veel wisselingen nodig zijn als de elementen in aflopende volgorde staan.

• 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 maximum aantal swaps is (1+2+3+4+…+N), oftewel N(N+1)/2, dus de ergste tijdcomplexiteit is O(N^2).

Hieronder vindt u de belangrijke tijdcomplexiteit van Insertion Sort:

• Ergste geval complexiteit: O(n^2): Het sorteren van een array in aflopende volgorde terwijl deze in oplopende volgorde moet worden gesorteerd, is het worstcasescenario.
• Beste geval complexiteit: O(n): Het beste geval doet zich voor wanneer de array al gesorteerd is; de buitenste lus wordt n keer uitgevoerd, terwijl de binnenste lus helemaal niet wordt uitgevoerd. Er zijn slechts n vergelijkingen, dus de complexiteit is lineair.
• Gemiddelde casuscomplexiteit: O(n^2): Dit gebeurt wanneer de elementen van de array in een willekeurige volgorde voorkomen die noch oplopend noch aflopend is.

Veelgestelde vragen