Insertion Sort: Algorithmus mit C, C++, Java, Python Beispiele

Was ist Einfügungssortierung?

Insertionsort ist einer der Vergleichssortieralgorithmen, die zum Sortieren von Elementen verwendet werden, indem jeweils ein Element durchlaufen und an der richtigen Position platziert wird.

Jedes Element wird nacheinander in eine bereits sortierte Liste eingefügt. Die Größe der bereits sortierten Liste beträgt zunächst eins. Der Einfügungssortierungsalgorithmus stellt sicher, dass die ersten k Elemente nach der k-ten Iteration sortiert werden.

Eigenschaften des Einfügungssortierungsalgorithmus

Der Algorithmus für Insertionsort hat folgende wichtige Eigenschaften:

• Es handelt sich um eine stabile Sortiertechnik, die die relative Reihenfolge gleicher Elemente nicht verändert.
• Es ist für kleinere Datensätze effizient, für größere Listen jedoch nicht effektiv.
• Die Einfügungssortierung ist adaptiv und reduziert die Gesamtzahl der Schritte, wenn sie teilweise sortiert ist. Feld wird als Input bereitgestellt, um es effizient zu machen.

Wie funktioniert Einfügen Operationsarbeit?

Im Insertion-Sort-Algorithmus wird die Einfügeoperation zum Sortieren unsortierter Elemente verwendet. Sie hilft dabei, ein neues Element in eine bereits sortierte Liste einzufügen.

Pseudocode der Einfügeoperation:

Betrachten Sie eine Liste A mit N Elementen.

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   

Im obigen Beispiel soll ein neues Element 6 in eine bereits sortierte Liste eingefügt werden.

Schritt 1) Im Vergleich zum linken Nachbarelement von A[5], 9 > 6, vertauschen wir die Position von 9 und 6. Jetzt wird Element 6 nach A[4] verschoben.

Schritt 2) Nun vergleichen wir A[4] und A[3] und stellen fest, dass A[3] > A[4], wir vertauschen erneut die Position von 6 und 8.

Schritt 3) Vergleichen Sie nun A[3] und A[2], da A[2] > A[3] die Position von 7 und 6 vertauscht.

Schritt 4) Wir vergleichen A[1] und A[2], und da A[1] < A[2] ist, ist das links benachbarte Element nicht mehr größer. Jetzt kommen wir zu dem Schluss, dass 6 korrekt eingefügt wurde, und stoppen den Algorithmus hier.

So funktioniert die Einfügesortierung

Der oben besprochene Einfügevorgang ist das Rückgrat des Insertionsort. Der Einfügevorgang wird für jedes Element ausgeführt und am Ende erhalten wir die sortierte Liste.

Die obige Beispielabbildung zeigt die Funktionsweise der Einfügungssortierung in der Datenstruktur. Anfangs ist nur ein Element in der sortierten Unterliste vorhanden, also 4. Nach dem Einfügen von A[1], also 3, wächst die Größe der sortierten Unterliste auf 2.

C++ Programm für Insertionsort

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

Ausgang:

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 Einfügungssortierung

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

Ausgang:

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

Python Programm für Insertionsort

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

Ausgang:

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

Eigenschaften der Einfügungssortierung

Hier sind wichtige Eigenschaften der Einfügungssortierung:

• Online: Die Einfügungssortierung kann Elemente beim Empfang sortieren. Das heißt, wenn wir bereits eine Liste von Elementen sortiert haben und weitere Elemente an die Listen anhängen, müssen wir nicht den gesamten Sortiervorgang erneut ausführen. Stattdessen müssen wir nur neu hinzugefügte Elemente iterieren.
• An Ort und Stelle: Die Speicherkomplexität des Insertionsort-Algorithmus ist konstant und erfordert keinen zusätzlichen Speicherplatz. Dieser Algorithmus sortiert Elemente an Ort und Stelle.
• Stabil: Bei der Einfügungssortierung vertauschen wir die Elemente nicht, wenn ihre Werte gleich sind. Wenn beispielsweise zwei Elemente, x und y, gleich sind und x in unsortierten Listen vor y erscheint, erscheint x in der sortierten Liste dann vor y. Dies macht die Einfügesortierung stabil.
• Adaptiv: A Sortieralgorithmus ist adaptiv, wenn es weniger Zeit benötigt, wenn die Eingabeelemente oder Teilmengen von Elementen bereits sortiert sind. Wie wir oben besprochen haben, beträgt die beste Laufzeit von Insertionsort O(N) und die schlechteste Laufzeit O(N^2). Insertionsort ist einer der adaptiven Sortieralgorithmen.

Komplexität des Insertionsort

Raumkomplexität

Das Insertionsort erfordert keinen zusätzlichen Speicherplatz zum Sortieren der Elemente, die Speicherplatzkomplexität ist konstant, d. h. O(1).

Zeitliche Komplexität

Da beim Insertionsort alle Elemente gleichzeitig durchlaufen werden, sind N-1 Durchgänge zum Sortieren von N Elementen erforderlich. Bei jedem Durchgang können Nullen vertauscht werden, wenn die Elemente bereits sortiert sind, oder es werden Elemente vertauscht, wenn die Elemente in absteigender Reihenfolge angeordnet sind.

• Für Durchgang 1 beträgt die erforderliche Mindestanzahl an Swaps Null und die maximal erforderliche Anzahl an Swaps beträgt 1.
• Für Durchgang 2 beträgt die erforderliche Mindestanzahl an Swaps Null und die maximal erforderliche Anzahl an Swaps beträgt 2.
• Für den Durchgang N beträgt der minimal erforderliche Swap Null und der maximal erforderliche Swap beträgt N.
• Der minimale Swap beträgt Null, sodass die beste Zeitkomplexität bei Iterationen mit N Durchläufen O(N) beträgt.
• Die Gesamtzahl der maximalen Swaps beträgt (1+2+3+4+..+N) i. N(N+1)/2, die schlechteste Zeitkomplexität ist O(N^2).

Hier ist die wichtige zeitliche Komplexität des Insertionsorts:

• Worst-Case-Komplexität: O(n2): Das Sortieren eines Arrays in absteigender Reihenfolge, wenn es in aufsteigender Reihenfolge vorliegt, ist das Worst-Case-Szenario.
• beste Fallkomplexität: O(n): Im besten Fall tritt Komplexität auf, wenn das Array bereits sortiert ist und die äußere Schleife n-mal ausgeführt wird, während die innere Schleife überhaupt nicht ausgeführt wird. Es gibt nur n Vergleiche. In diesem Fall ist die Komplexität also linear.
• Durchschnittliche Fallkomplexität: O(n2): Dies geschieht, wenn die Elemente eines Arrays in einer durcheinandergebrachten Reihenfolge auftreten, also weder aufsteigend noch absteigend.

Zusammenfassung

• Einfügungssortierung ist eine Sortieralgorithmusmethode, die auf dem Vergleich basiert.
• Es handelt sich um eine stabile Sortiertechnik, die die relative Reihenfolge gleicher Elemente nicht verändert.
• Bei jedem Element wird die Einfügeoperation verwendet, um das Element in die sortierte Unterliste einzufügen.
• Einfügungssortierung ist ein In-Place-Sortieralgorithmus.
• Die schlechteste und durchschnittliche Zeitkomplexität des Insertionsort ist quadratisch, d. h. O(N^2).
• Für die Einfügungssortierung ist kein Hilfsraum erforderlich.