Einfügesortierungsalgorithmus in C, C++, Java, Python Beispiele

Was ist Einfügungssortierung?

Insertion Sort ist einer der Vergleichssortieralgorithmen, die zum Sortieren von Elementen verwendet werden, indem jeweils ein Element durchlaufen und an der richtigen Position innerhalb eines bereits sortierten Bereichs platziert wird.

Jedes Element wird nacheinander in eine bereits sortierte Liste eingefügt. Die anfängliche Größe dieser Liste beträgt eins. Der Insertion-Sort-Algorithmus stellt sicher, dass die ersten k Elemente nach der k-ten Iteration der äußeren Schleife sortiert sind.

Da Insertion Sort das Ergebnis inkrementell aufbaut, ist es intuitiv zu lehren, leicht zu debuggen und eine solide Grundlage für sehr kleine Eingaben, bei denen komplexere Algorithmen zusätzlichen Aufwand ohne messbare Vorteile bringen würden.

Eigenschaften des Einfügungssortierungsalgorithmus

Der Algorithmus für Insertion Sort weist folgende wichtige Merkmale auf, die sein Verhalten bei realen Arbeitslasten erklären:

• Es handelt sich um eine stabile Sortiertechnik, die die relative Reihenfolge gleicher Elemente nicht verändert.
• Für kleinere Datensätze ist es effizient, für größere Listen, bei denen das quadratische Wachstum dominiert, jedoch nicht effektiv.
• Der Insertion Sort-Algorithmus ist adaptiv, d. h., er reduziert die Gesamtzahl seiner Schritte, wenn die Eingabe teilweise sortiert ist. Feld wird als Eingabe bereitgestellt, um die Effizienz zu steigern, da der wahlfreie Zugriff Verschiebungen in konstanter Zeit während der inneren Schleife ermöglicht.
• Es handelt sich um einen In-Place-Algorithmus, daher ist kein zusätzlicher Speicherplatz proportional zur Eingabegröße erforderlich.

Unter Berücksichtigung dieser Eigenschaften wird im nächsten Abschnitt die zentrale Einfügeoperation erläutert, die jedem Durchlauf des Algorithmus zugrunde liegt.

Wie funktioniert Einfügen Operationsarbeit?

Beim Insertion Sort-Algorithmus wird die Einfügeoperation verwendet, um unsortierte Elemente zu sortieren. Sie ermöglicht das Einfügen eines neuen Elements in eine bereits sortierte Liste unter Beibehaltung der bestehenden Reihenfolge des sortierten Bereichs.

Pseudocode der Einfügeoperation:

Betrachten Sie eine Liste A mit N Elementen.

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

Im obigen Beispiel wird ein neues Element 6 in eine bereits sortierte Liste eingefügt. Die folgenden Schritte tracDie innere Schleife wird durchlaufen, während das neue Element nach links in Richtung seiner korrekten Position wandert.

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] ist, also tauschen wir erneut die Position von 6 und 8.

Schritt 3) Vergleichen wir nun A[3] und A[2]. Da A[2] > A[3], tauschen wir die Positionen von 7 und 6.

Schritt 4) Wir vergleichen A[1] und A[2]. Da A[1] < A[2], ist das links benachbarte Element nicht mehr größer. Wir schließen daraus, dass 6 korrekt eingefügt wurde, und beenden die innere Schleife an dieser Stelle.

So funktioniert die Einfügesortierung

Die oben beschriebene Einfügeoperation ist das Kernstück des Insertion Sort-Algorithmus. Die Einfügeprozedur wird für jedes Element ausgeführt, und am Ende erhalten wir die sortierte Liste, da der sortierte Bereich bei jedem äußeren Durchlauf um ein Element wächst.

Die obige Abbildung veranschaulicht die Funktionsweise des Insertion Sort-Algorithmus in einer Datenstruktur. Anfangs enthält die sortierte Teilliste nur ein Element, nämlich 4. Nach dem Einfügen von A[1], also 3, wächst die Größe der sortierten Teilliste auf 2, und der Algorithmus setzt dieses Muster fort, bis jedes Element eingefügt wurde.

Nachdem der konzeptionelle Ablauf erläutert wurde, zeigen die folgenden Abschnitte konkrete Umsetzungen in C++, C und Python So können Sie Schleifenstrukturen über verschiedene Sprachen hinweg vergleichen.

C++ Programm für Insertionsort

Das C++ Die untenstehende Implementierung verwendet zwei verschachtelte Schleifen: Die äußere Schleife wählt das nächste unsortierte Element aus, und die innere Schleife verschiebt es nach links, bis die richtige Position gefunden ist.

#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ügesortierung

Dieselbe Logik lässt sich direkt auf C übertragen. Der Standard printf Die Aufrufe ersetzen die Stream-Ausgabe, aber das Tauschmuster innerhalb der inneren Schleife ist identisch mit dem der 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;
}

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

Python Unterstützt Tupeltauschping in einem einzigen Ausdruck, sodass die innere Schleife kompakter ist als ihre C-Schleife und C++ Gegenstücke unter Beibehaltung des gleichen algorithmischen Verhaltens.

#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 des Insertion Sort-Algorithmus, die Ihnen bei der Entscheidung helfen, wann er das richtige Werkzeug ist:

• Online: Der Insertion Sort-Algorithmus sortiert Elemente, sobald sie ihm zugeführt werden. Wenn eine Liste von Elementen bereits sortiert ist und weitere Elemente hinzugefügt werden, muss der Sortiervorgang nicht erneut ausgeführt werden. Stattdessen werden nur die neu hinzugefügten Elemente verarbeitet.
• An Ort und Stelle: Der Insertionsort-Algorithmus hat eine konstante Speicherkomplexität und benötigt keinen zusätzlichen Speicherplatz. Er sortiert die Elemente direkt im Speicher.
• Stabil: Beim Einfügesortieralgorithmus werden Elemente nicht vertauscht, wenn ihre Werte gleich sind. Wenn beispielsweise zwei Elemente, x und y, gleich sind und x in der unsortierten Liste vor y steht, dann steht x auch in der sortierten Liste vor y. Dies macht den Einfügesortieralgorithmus stabil.
• Adaptiv: A Sortieralgorithmus Ein Sortieralgorithmus ist adaptiv, wenn er weniger Zeit benötigt, sobald die Eingabeelemente oder eine Teilmenge davon sortiert sind. Wie bereits erwähnt, liegt die beste Laufzeit von Insertion Sort bei O(N), die schlechteste bei O(N²). Insertion Sort zählt zu den adaptiven Sortieralgorithmen.

Komplexität des Insertionsort

Die nachfolgende Komplexitätsdiskussion umfasst sowohl Speichernutzung als auch Laufzeit, sodass Sie Insertion Sort mit Alternativen wie beispielsweise … vergleichen können. Bubble Sortieren und Schnelle Sorte.

Raumkomplexität

Der Insertion Sort-Algorithmus benötigt keinen zusätzlichen Speicherplatz zum Sortieren der Elemente. Die Speicherkomplexität ist konstant, d. h. O(1), da unabhängig von der Eingabegröße nur wenige temporäre Variablen verwendet werden.

Zeitliche Komplexität

Da der Insertion Sort-Algorithmus jeweils ein Element verarbeitet, benötigt er N-1 Durchläufe, um N Elemente zu sortieren. Bei jedem Durchlauf sind möglicherweise keine Vertauschungen nötig, wenn die Elemente bereits sortiert sind, oder es können viele Vertauschungen erforderlich sein, 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 maximale Gesamtzahl an Tauschvorgängen beträgt (1+2+3+4+…+N), d.h. N(N+1)/2, sodass die schlechteste Zeitkomplexität O(N^2) beträgt.

Hier die wichtige Zeitkomplexität des Insertion Sort-Algorithmus:

• Worst-Case-KomplexitätO(n^2): Das Sortieren eines Arrays in absteigender Reihenfolge, wenn es aufsteigend sortiert werden soll, ist der schlimmste Fall.
• beste Fallkomplexität: O(n): Der beste Fall tritt ein, wenn das Array bereits sortiert ist; die äußere Schleife wird n-mal durchlaufen, die innere Schleife hingegen gar nicht. Da nur n Vergleiche erforderlich sind, ist die Komplexität linear.
• Durchschnittliche Fallkomplexität: O(n^2): Dies tritt auf, wenn die Elemente des Arrays in einer durcheinandergewürfelten Reihenfolge vorliegen, die weder aufsteigend noch absteigend ist.

Häufig gestellte Fragen