Innsettingssortering: Algoritme med C, C++, Java, Python Eksempler

Hva er innsettingssortering?

Innsettingssortering er en av sammenligningssorteringsalgoritmene som brukes til å sortere elementer ved å iterere på ett element om gangen og plassere elementet i riktig posisjon.

Hvert element settes sekvensielt inn i en allerede sortert liste. Størrelsen på den allerede sorterte listen er i utgangspunktet én. Innsettingssorteringsalgoritmen sikrer at de første k elementene blir sortert etter den kth iterasjonen.

Kjennetegn ved innsettingssorteringsalgoritme

Algoritmen for innsettingssortering har følgende viktige egenskaper:

• Det er en stabil sorteringsteknikk, så den endrer ikke den relative rekkefølgen av like elementer.
• Det er effektivt for mindre datasett, men ikke effektivt for større lister.
• Innsettingssortering er adaptiv, noe som reduserer det totale antallet trinn hvis det er delvis sortert. Array er gitt som input for å gjøre det effektivt.

Hvordan setter inn Operasjonsarbeid?

I Insertion Sort-algoritmen brukes innsettingsoperasjonen til å sortere usorterte elementer. Det hjelper å sette inn et nytt element i en allerede sortert liste.

Pseudokode for innsettingsoperasjon:

Tenk på en liste A med N elementer.

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   

I eksemplet ovenfor skal et nytt element 6 settes inn i en allerede sortert liste.

Trinn 1) Sammenlignet med det venstre tilstøtende elementet til A[5], 9 > 6, bytter vi posisjonen til 9 og 6. Nå flyttes element 6 til A[4].

Trinn 2) Nå sammenligner vi A[4] og A[3], og vi finner at A[3] > A[4], vi bytter igjen posisjonen til 6 og 8.

Trinn 3) Sammenlign nå A[3] og A[2], da A[2] > A[3] bytter posisjonen 7 og 6.

Trinn 4) Vi sammenligner A[1] og A[2], og som A[1] < A[2], dvs. det venstre tilstøtende elementet er ikke lenger større. Nå konkluderer vi med at 6 er satt inn riktig, og vi stopper algoritmen her.

Slik fungerer innsettingssortering

Innsettingsoperasjonen diskutert ovenfor er ryggraden i innsettingssorten. Innsettingsprosedyren utføres på hvert element, og til slutt får vi den sorterte listen.

Eksempelfiguren ovenfor viser hvordan innsettingssortering fungerer i datastruktur. Til å begynne med er det bare ett element i den sorterte underlisten, dvs. 4. Etter å ha satt inn A[1], dvs. 3, vokser størrelsen på den sorterte underlisten til 2.

C++ Program for innsettingssortering

#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;
}

Utgang:

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

C Code for innsettingssortering

#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;
}

Utgang:

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 for innsettingssortering

#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=" ")

Utgang:

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

Egenskaper for innsettingssortering

Her er viktige egenskaper for innsettingssortering:

• På nett: Innsettingssortering kan sortere elementer etter hvert som den mottas. Det vil si at hvis vi allerede har sortert en liste med elementer og lagt til noen flere elementer i listene, trenger vi ikke å kjøre hele sorteringsprosedyren på nytt. I stedet trenger vi bare å iterere på nylig lagt til elementer.
• På plass: Plasskompleksiteten til innsettingssorteringsalgoritmen er konstant og krever ikke ekstra plass. Denne algoritmen sorterer elementer på plass.
• Stabil: Ved innsettingssortering bytter vi ikke elementene hvis verdiene deres er like. For eksempel, to elementer, x og y, er like, og x vises før y i usorterte lister, så i den sorterte listen vil x vises før y. Dette gjør innsettingssortering stabil.
• Tilpasningsdyktig: A sorteringsalgoritme er adaptiv hvis det tar kortere tid hvis inngangselementene eller undergruppen av elementer allerede er sortert. Som vi diskuterte ovenfor, er den beste kjøretiden for innsettingssortering O(N), og den dårligste kjøretiden er O(N^2). Innsettingssortering er en av de adaptive sorteringsalgoritmene.

Kompleksiteten til innsettingssortering

Romkompleksitet

Innsettingssorteringen krever ikke ekstra plass for å sortere elementene, romkompleksiteten er konstant, dvs. O(1).

Tidskompleksitet

Ettersom innsettingssortering itererer hvert element samtidig, krever det N-1 passeringer for å sortere N elementer. For hvert pass kan det gjøre nullbytter hvis elementene allerede er sortert, eller bytte hvis elementene er ordnet i synkende rekkefølge.

• For pass 1 er minimumsbyttekravene null, og maksimumsbyttekravene er 1.
• For pass 2 er minimumsbyttekravene null, og maksimumsbyttekravene er 2.
• For pass N er minimumsbyttet som kreves null, og maksimumsbyttet som kreves er N.
• Minimumsbyttet er null, så den beste tidskompleksiteten er O(N) for iterering av N passeringer.
• Totale maksimumsbytter er (1+2+3+4+..+N) i. N(N+1)/2, den verste tidskompleksiteten er O(N^2).

Her er den viktige tidskompleksiteten til innsettingssortering:

• Worst Case Complexity: O(n2): Sortering av en matrise i synkende rekkefølge når den er i stigende rekkefølge er det verste scenarioet.
• Beste sakskompleksitet: O(n): Best Case Complexity oppstår når matrisen allerede er sortert, den ytre sløyfen kjører n antall ganger mens den indre sløyfen ikke kjører i det hele tatt. Det er bare n antall sammenligninger. Så i dette tilfellet er kompleksiteten lineær.
• Gjennomsnittlig sakskompleksitet: O(n2): Det skjer når elementene i en matrise forekommer i den sammenslåtte rekkefølgen, som verken er stigende eller synkende.

Sammendrag

• Innsettingssortering er en sorteringsalgoritme som er basert på sammenligningen.
• Det er en stabil sorteringsteknikk, så den endrer ikke den relative rekkefølgen av like elementer.
• På hvert element brukes innsettingsoperasjonen for å sette inn elementet i den sorterte underlisten.
• Innsettingssortering er en in-place sorteringsalgoritme.
• Den verste og gjennomsnittlige tidskompleksiteten til innsettingssortering er kvadratisk, dvs. O(N^2).
• Innsettingssortering krever ingen ekstra plass.