Innsettingssorteringsalgoritme med C, C++, Java, Python Eksempler

Hva er innsettingssortering?

Innsettingssortering er en av sammenligningsalgoritmene som brukes til å sortere elementer ved å iterere på ett element om gangen og plassere elementet i riktig posisjon i et allerede ordnet område.

Hvert element settes sekvensielt inn i en allerede sortert liste. Størrelsen på den allerede sorterte listen er i utgangspunktet én. Insertion Sort-algoritmen sørger for at de første k elementene sorteres etter den k-te iterasjonen av den ytre løkken.

Fordi Insert Sort bygger resultatet trinnvis, er det intuitivt å lære bort, enkelt å feilsøke og et sterkt grunnlag for svært små inndata der mer komplekse algoritmer ville legge til overhead uten målbare gevinster.

Kjennetegn ved innsettingssorteringsalgoritme

Algoritmen for innsettingssortering har følgende viktige egenskaper som forklarer dens oppførsel på reelle arbeidsbelastninger:

• 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 der kvadratisk vekst dominerer.
• Insert Sort er adaptiv, noe som reduserer det totale antallet trinn hvis inputen er delvis sortert. Array gis som input for å gjøre den effektiv fordi tilfeldig tilgang muliggjør konstante tidsskift i løpet av den indre sløyfen.
• Det er en på stedet-algoritme, så den krever ikke tilleggslagring proporsjonal med inngangsstørrelsen.

Med disse egenskapene i tankene forklarer neste avsnitt den sentrale innsettingsoperasjonen som driver hvert pass i algoritmen.

Hvordan setter inn Operasjonsarbeid?

I algoritmen for innsettingssortering brukes innsettingsoperasjonen til å sortere usorterte elementer. Den hjelper med å sette inn et nytt element i en allerede sortert liste samtidig som den eksisterende rekkefølgen i det sorterte området bevares.

Pseudokode for innsettingsoperasjonen:

Tenk på 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 eksemplet ovenfor settes et nytt element 6 inn i en allerede sortert liste. Følgende trinn trace den indre sløyfen når det nye elementet migrerer til venstre mot sin riktige posisjon.

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], så vi bytter igjen om posisjonen til 6 og 8.

Trinn 3) Sammenlign nå A[3] og A[2]. Siden A[2] > A[3], bytter vi om på plasseringen til 7 og 6.

Trinn 4) Vi sammenligner A[1] og A[2]. Siden A[1] < A[2], er ikke det venstre tilstøtende elementet lenger større. Vi konkluderer med at 6 er satt inn riktig, og vi stopper den indre løkken her.

Slik fungerer innsettingssortering

Innsettingsoperasjonen som er omtalt ovenfor er ryggraden i Insert Sort. Innsettingsprosedyren utføres på hvert element, og til slutt får vi den sorterte listen etter hvert som det sorterte området vokser med ett element for hver ytre passasje.

Figuren ovenfor demonstrerer hvordan innsettingssortering fungerer i en datastruktur. I utgangspunktet er det bare ett element i den sorterte dellisten, dvs. 4. Etter at A[1], dvs. 3, er satt inn, vokser størrelsen på den sorterte dellisten til 2, og algoritmen fortsetter dette mønsteret til alle elementene er plassert.

Med den konseptuelle flyten på plass viser de følgende avsnittene konkrete implementeringer i C++, C og Python slik at du kan sammenligne løkkestrukturer på tvers av språk.

C++ Program for innsettingssortering

Ocuco C++ Implementeringen nedenfor bruker to nestede løkker: den ytre løkken velger det neste usorterte elementet, og den indre løkken flytter det til venstre til riktig posisjon er funnet.

#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

Den samme logikken oversettes direkte til C. Standarden printf anrop erstatter strømutgang, men byttemønsteret inne i den indre sløyfen er identisk med C++ versjon.

#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

Python støtter tuppelbytteping i et enkelt uttrykk, slik at den indre løkken er mer kompakt enn dens C og C++ motparter samtidig som den samme algoritmiske oppførselen 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=" ")

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 ved innsettingssortering som hjelper deg med å avgjøre når det er riktig verktøy:

• På nett: Insert Sort kan sortere elementer etter hvert som den mottar dem. Hvis vi allerede har sortert en liste med elementer og legger til flere elementer i listen, trenger vi ikke å kjøre hele sorteringsprosedyren på nytt. I stedet itererer vi bare på de nylig tillagte elementene.
• På plass: Romkompleksiteten til Insertion Sort-algoritmen er konstant og krever ikke ekstra plass. Denne algoritmen sorterer elementer på plass.
• Stabil: I innsettingssortering bytter vi ikke elementer hvis verdiene deres er like. Hvis for eksempel to elementer, x og y, er like og x vises før y i den usorterte listen, vil x fortsatt vises før y i den sorterte listen. Dette gjør innsettingssortering stabil.
• Tilpasningsdyktig: A sorteringsalgoritme er adaptiv hvis det tar kortere tid når input-elementene eller et delsett av elementer allerede er sortert. Som vi diskuterte ovenfor, er den beste kjøretiden for Insert Sort O(N), og den verste kjøretiden er O(N^2). Insert Sort er en av de adaptive sorteringsalgoritmene.

Kompleksiteten til innsettingssortering

Kompleksitethetsdiskusjonen nedenfor dekker både minnebruk og kjøretid, slik at du kan plassere Insert Sort mot alternativer som Bubble Sorter og Rask sortering.

Romkompleksitet

Innsettingssortering krever ikke ekstra plass for å sortere elementene. Romkompleksiteten er konstant, dvs. O(1), fordi bare noen få midlertidige variabler brukes uavhengig av inputstørrelsen.

Tidskompleksitet

Fordi Insertion Sort itererer ett element om gangen, krever det N-1 gjennomganger for å sortere N elementer. For hver gjennomgang kan det hende at det ikke blir gjort noen bytter hvis elementene allerede er sortert, eller det kan være behov for mange bytter 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.
• Totalt antall maksimale bytter er (1+2+3+4+…+N), dvs. N(N+1)/2, så den verste tidskompleksiteten er O(N^2).

Her er den viktige tidskompleksiteten til innsettingssortering:

• Worst Case ComplexityO(n^2): Å sortere en matrise i synkende rekkefølge når den skal være stigende er verst tenkelige scenario.
• Beste sakskompleksitet: O(n): Det beste tilfellet oppstår når matrisen allerede er sortert; den ytre løkken kjører n ganger, mens den indre løkken ikke kjører i det hele tatt. Det er bare n sammenligninger, så kompleksiteten er lineær.
• Gjennomsnittlig sakskompleksitet: O(n^2): Dette skjer når elementene i tabellen opptrer i en blandet rekkefølge som verken er stigende eller synkende.

Spørsmål og svar