Indsættelsessorteringsalgoritme med C, C++, Java, Python Eksempler

Hvad er indsættelsessortering?

Indsættelsessortering er en af ​​de sammenligningsalgoritmer, der bruges til at sortere elementer ved at iterere på ét element ad gangen og placere elementet på dets korrekte position inden for et allerede ordnet område.

Hvert element indsættes sekventielt i en allerede sorteret liste. Størrelsen på den allerede sorterede liste er initialt én. Insertion Sort-algoritmen sikrer, at de første k elementer sorteres efter den k'te iteration af den ydre løkke.

Fordi Insertion Sort opbygger resultatet trinvis, er det intuitivt at undervise i, nemt at fejlfinde og en stærk basislinje for meget små input, hvor mere komplekse algoritmer ville øge overhead uden målbare gevinster.

Karakteristika for indsættelsessorteringsalgoritme

Algoritmen til indsættelsessortering har følgende vigtige egenskaber, der forklarer dens opførsel på reelle arbejdsbelastninger:

• Det er en stabil sorteringsteknik, så den ændrer ikke den relative rækkefølge af lige store elementer.
• Det er effektivt for mindre datasæt, men ikke effektivt for større lister, hvor kvadratisk vækst dominerer.
• Indsættelsessortering er adaptiv, hvilket reducerer det samlede antal trin, hvis inputtet er delvist sorteret. Array leveres som input for at gøre det effektivt, fordi tilfældig adgang muliggør konstante tidsforskydninger under den indre løkke.
• Det er en in-place algoritme, så den kræver ikke ekstra lagring proportionalt med inputstørrelsen.

Med disse træk i tankerne forklarer næste afsnit den centrale indsættelsesoperation, der driver hvert gennemløb af algoritmen.

Hvordan indsætter Operation arbejde?

I indsættelsessorteringsalgoritmen bruges indsættelsesoperationen til at sortere usorterede elementer. Den hjælper med at indsætte et nyt element i en allerede sorteret liste, samtidig med at den eksisterende rækkefølge i det sorterede område bevares.

Pseudokode for indsættelsesoperationen:

Overvej en liste A med N elementer.

// 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

I ovenstående eksempel indsættes et nyt element 6 i en allerede sorteret liste. Følgende trin trace den indre løkke, når det nye element migrerer til venstre mod sin korrekte position.

Trin 1) Sammenlignet med det venstre tilstødende element af A[5], 9 > 6, bytter vi positionen af ​​9 og 6. Nu flyttes element 6 til A[4].

Trin 2) Nu sammenligner vi A[4] og A[3], og vi finder, at A[3] > A[4], så vi bytter igen om på positionen af ​​6 og 8.

Trin 3) Sammenlign nu A[3] og A[2]. Da A[2] > A[3], bytter vi om på positionerne for 7 og 6.

Trin 4) Vi sammenligner A[1] og A[2]. Da A[1] < A[2], er det venstre tilstødende element ikke længere større. Vi konkluderer, at 6 er indsat korrekt, og vi stopper den indre løkke her.

Sådan fungerer indsættelsessortering

Den ovenfor omtalte indsættelsesoperation er rygraden i indsættelsessortering. Indsættelsesproceduren udføres på hvert element, og til sidst får vi den sorterede liste, efterhånden som det sorterede område vokser med et element for hver ydre passage.

Figuren ovenfor demonstrerer, hvordan indsættelsessortering fungerer i en datastruktur. I starten er der kun ét element i den sorterede delliste, dvs. 4. Efter indsættelse af A[1], dvs. 3, vokser størrelsen af ​​den sorterede delliste til 2, og algoritmen fortsætter dette mønster, indtil alle elementer er blevet placeret.

Med det konceptuelle flow på plads viser de følgende afsnit konkrete implementeringer i C++, C og Python så du kan sammenligne loopstrukturer på tværs af sprog.

C++ Program til indsættelsessortering

C++ Implementeringen nedenfor bruger to indbyggede løkker: den ydre løkke vælger det næste usorterede element, og den indre løkke flytter det til venstre, indtil den korrekte position er fundet.

#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 til indsættelsessortering

Den samme logik overføres direkte til C. Standarden printf kald erstatter stream output, men swap-mønsteret i den indre løkke er identisk med C++ version.

#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 Program til indsættelsessortering

Python understøtter tuple-bytteping i et enkelt udtryk, så den indre løkke er mere kompakt end dens C og C++ modparter, samtidig med at den samme algoritmiske adfærd bevares.

#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

Egenskaber for indsættelsessortering

Her er vigtige egenskaber ved indsættelsessortering, der hjælper dig med at beslutte, hvornår det er det rigtige værktøj:

• Online: Insertion Sort kan sortere elementer, efterhånden som den modtager dem. Hvis vi allerede har sorteret en liste af elementer og tilføjer flere elementer til listen, behøver vi ikke at køre hele sorteringsproceduren igen. I stedet itererer vi kun på de nyligt tilføjede elementer.
• På plads: Rumkompleksiteten i Insertion Sort-algoritmen er konstant og kræver ikke ekstra plads. Denne algoritme sorterer elementer på plads.
• stabil: I indsættelsessortering bytter vi ikke om på elementer, hvis deres værdier er ens. Hvis for eksempel to elementer, x og y, er ens, og x vises før y i den usorterede liste, vil x stadig vises før y i den sorterede liste. Dette gør indsættelsessortering stabil.
• Fleksibel: A sorteringsalgoritme er adaptiv, hvis det tager kortere tid, når inputelementerne eller en delmængde af elementer allerede er sorteret. Som vi diskuterede ovenfor, er den bedste køretid for Insertion Sort O(N), og den værste køretid er O(N^2). Insertion Sort er en af ​​de adaptive sorteringsalgoritmer.

Indsættelsessorterings kompleksitet

Kompleksitetsdiskussionen nedenfor dækker både hukommelsesforbrug og kørselstid, så du kan placere indsættelsessortering i forhold til alternativer som f.eks. Bubble Sortere og Hurtig sortering.

Rumkompleksitet

Indsættelsessortering kræver ikke ekstra plads for at sortere elementerne. Pladskompleksiteten er konstant, dvs. O(1), fordi kun få midlertidige variabler bruges uanset inputstørrelsen.

Tidskompleksitet

Da Insertion Sort itererer ét element ad gangen, kræver det N-1 gennemløb for at sortere N elementer. For hver gennemgang kan den foretage nul ombytninger, hvis elementerne allerede er sorteret, eller den kan kræve mange ombytninger, hvis elementerne er arrangeret i faldende rækkefølge.

• For pass 1 er de krævede minimumsswaps nul, og de maksimale krævede swaps er 1.
• For pass 2 er de krævede minimumsswaps nul, og de maksimale krævede swaps er 2.
• For pass N er minimumsbyttet påkrævet nul, og det maksimale krævede bytte er N.
• Minimumsswap er nul, så den bedste tidskompleksitet er O(N) til iteration af N gennemløb.
• Det samlede maksimale antal swaps er (1+2+3+4+…+N), dvs. N(N+1)/2, så den værste tidskompleksitet er O(N^2).

Her er den vigtige tidskompleksitet ved indsættelsessortering:

• Worst Case ComplexityO(n^2): Det værst tænkelige scenarie er at sortere et array i faldende rækkefølge, når det skal være stigende.
• Bedste sags kompleksitet: O(n): Det bedste tilfælde forekommer, når arrayet allerede er sorteret; den ydre løkke kører n gange, mens den indre løkke slet ikke kører. Der er kun n sammenligninger, så kompleksiteten er lineær.
• Gennemsnitlig sagskompleksitet: O(n^2): Dette sker, når elementerne i et array forekommer i en rodet rækkefølge, der hverken er stigende eller faldende.

Ofte Stillede Spørgsmål