Insättningssorteringsalgoritm med C, C++, Java, Python Exempel

Vad är insättningssortering?

Insertion Sort är en av de jämförelsesorteringsalgoritmer som används för att sortera element genom att iterera på ett element i taget och placera elementet på rätt position inom en redan ordnad region.

Varje element infogas sekventiellt i en redan sorterad lista. Storleken på den redan sorterade listan är initialt ett. Insertion Sort-algoritmen säkerställer att de första k elementen sorteras efter den k:te iterationen av den yttre loopen.

Eftersom Insertion Sort bygger resultatet stegvis är det intuitivt att lära ut, enkelt att felsöka och en stark baslinje för mycket små indata där mer komplexa algoritmer skulle öka kostnaden utan mätbara vinster.

Egenskaper för insättningssorteringsalgoritm

Algoritmen för Insertion Sort har följande viktiga egenskaper som förklarar dess beteende på verkliga arbetsbelastningar:

• Det är en stabil sorteringsteknik, så den ändrar inte den relativa ordningen för lika element.
• Det är effektivt för mindre datamängder men inte effektivt för större listor där kvadratisk tillväxt dominerar.
• Insertion Sort är adaptiv, vilket minskar det totala antalet steg om inmatningen är delvis sorterad. array tillhandahålls som indata för att göra den effektiv eftersom slumpmässig åtkomst möjliggör konstanta tidsförskjutningar under den inre loopen.
• Det är en på plats-algoritm, så den kräver inte extra lagring proportionellt mot indatastorleken.

Med dessa egenskaper i åtanke förklarar nästa avsnitt den centrala insert-operationen som driver varje pass i algoritmen.

Hur sätts in Operation arbete?

I algoritmen Insert Sort används insert-operationen för att sortera osorterade element. Den hjälper till att infoga ett nytt element i en redan sorterad lista samtidigt som den befintliga ordningen i det sorterade området bevaras.

Pseudokod för insert-operationen:

Betrakta en lista A med N element.

// 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 exemplet ovan infogas ett nytt element 6 i en redan sorterad lista. Följande steg tracden inre slingan när det nya elementet migrerar åt vänster mot sin korrekta position.

Steg 1) Jämfört med det vänstra intilliggande elementet av A[5], 9 > 6, byter vi positionen för 9 och 6. Nu flyttas element 6 till A[4].

Steg 2) Nu jämför vi A[4] och A[3], och vi finner att A[3] > A[4], så vi byter plats på 6 och 8 igen.

Steg 3) Jämför nu A[3] och A[2]. Eftersom A[2] > A[3] byter vi plats på 7 och 6.

Steg 4) Vi jämför A[1] och A[2]. Eftersom A[1] < A[2] är det vänstra intilliggande elementet inte längre större. Vi drar slutsatsen att 6 är korrekt infogat, och vi stoppar den inre slingan här.

Hur insättningssorteringen fungerar

Insert-operationen som diskuterats ovan är grunden för Insert Sort. Insert-proceduren körs på varje element, och i slutet får vi den sorterade listan allt eftersom det sorterade området växer med ett element för varje yttre pass.

Figuren ovan visar hur insättningssortering fungerar i en datastruktur. Inledningsvis finns endast ett element i den sorterade dellistan, dvs. 4. Efter att A[1], dvs. 3, har infogat den sorterade dellistan, växer storleken till 2, och algoritmen fortsätter detta mönster tills alla element har placerats.

Med det konceptuella flödet på plats visar följande avsnitt konkreta implementeringar i C++, C och Python så att du kan jämföra loopstrukturer mellan språk.

C++ Program för insättningssortering

Ocuco-landskapet C++ Implementeringen nedan använder två kapslade loopar: den yttre loopen väljer nästa osorterade element, och den inre loopen flyttar det åt vänster tills rätt position hittas.

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

Produktion:

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

C Code för insättningssortering

Samma logik översätts direkt till C. Standarden printf anrop ersätter strömutgång, men bytesmönstret inuti den inre loopen är identiskt med C++ versionen.

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

Produktion:

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 för insättningssortering

Python stöder tupelbyteping i ett enda uttryck, så den inre loopen är mer kompakt än dess C och C++ motsvarigheter samtidigt som samma algoritmiska beteende bibehålls.

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

Produktion:

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

Egenskaper för insättningssortering

Här är viktiga egenskaper hos Insertion Sort som hjälper dig att avgöra när det är rätt verktyg:

• Uppkopplad: Insertion Sort kan sortera element allt eftersom de tas emot. Om vi ​​redan har sorterat en lista med element och lägger till fler element i listan behöver vi inte köra hela sorteringsproceduren igen. Istället itererar vi bara på de nyligen tillagda elementen.
• På plats: Rymdkomplexiteten hos Insertion Sort-algoritmen är konstant och kräver inget extra utrymme. Denna algoritm sorterar element på plats.
• Stabil: I insättningssortering byter vi inte element om deras värden är lika. Om till exempel två element, x och y, är lika och x visas före y i den osorterade listan, så kommer x fortfarande att visas före y i den sorterade listan. Detta gör insättningssortering stabil.
• Anpassningsbar: A sorteringsalgoritm är adaptiv om det tar kortare tid när ingångselementen eller en delmängd av element redan är sorterade. Som vi diskuterade ovan är den bästa körtiden för insättningssortering O(N), och den sämsta körtiden är O(N^2). Insättningssortering är en av de adaptiva sorteringsalgoritmerna.

Insättningssorteringens komplexitet

Komplexitetsdiskussionen nedan täcker både minnesanvändning och körtid så att du kan placera Insertion Sort mot alternativ som Bubble Sortera och Snabb sortering.

Rymdkomplexitet

Insertion Sort kräver inte extra utrymme för att sortera elementen. Rymdskomplexiteten är konstant, dvs. O(1), eftersom endast ett fåtal temporära variabler används oavsett inmatningsstorlek.

Tidskomplexitet

Eftersom Insertion Sort itererar ett element i taget krävs det N-1 omgångar för att sortera N element. För varje omgång kan det göra noll byten om elementen redan är sorterade, eller det kan behöva många byten om elementen är ordnade i fallande ordning.

• För pass 1 är de minsta erforderliga bytena noll och de maximala bytena som krävs är 1.
• För pass 2 är de minsta erforderliga bytena noll och de maximala bytena som krävs är 2.
• För pass N är det minsta swap som krävs noll, och det maximala swap som krävs är N.
• Minsta swap är noll, så den bästa tidskomplexiteten är O(N) för att iterera N pass.
• Totalt maximalt antal swappar är (1+2+3+4+…+N), dvs. N(N+1)/2, så den värsta tidskomplexiteten är O(N^2).

Här är den viktiga tidskomplexiteten för insättningssortering:

• Worst Case ComplexityO(n^2): Att sortera en array i fallande ordning när den måste vara stigande är det värsta tänkbara scenariot.
• Best Case-komplexitet: O(n): Det bästa fallet inträffar när arrayen redan är sorterad; den yttre loopen körs n gånger, medan den inre loopen inte körs alls. Det finns bara n jämförelser, så komplexiteten är linjär.
• Genomsnittlig ärendekomplexitet: O(n^2): Detta händer när elementen i en array förekommer i en blandad ordning som varken är stigande eller fallande.

Vanliga frågor