Einfügung Sortierung

Harshit Jindal 12 Oktober 2023
  1. Einfüge-Sortieralgorithmus
  2. Beispiel für Einfügungssortierung
  3. Implementierung des Einfügungs-Sortieralgorithmus
  4. Komplexität des Einfüge-Sortieralgorithmus
Einfügung Sortierung

Einfügungssortierung ist ein einfacher vergleichsbasierter Sortieralgorithmus. Bei diesem Algorithmus werden zwei Teilarrays verwaltet: ein sortiertes und ein unsortiertes Teilarray. Ein Element aus dem unsortierten Subarray findet seine richtige Position im sortierten Subarray und wird dort eingefügt. Das ist analog zu der Art und Weise, wie jemand ein Kartenspiel auf der Hand sortiert. Es wird Einfügesortierung genannt, weil es darauf abzielt, ein Element an seiner richtigen Position einzufügen. Dieser Algorithmus ist effizient für kleine Datensätze, aber nicht geeignet für große Datensätze.

Einfüge-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben. Das erste Element, A[0], ist bereits sortiert und befindet sich im sortierten Subarray.

  • Wir markieren das erste Element aus dem unsortierten Subarray A[1] als Schlüssel.
  • Der Schlüssel wird dann mit Elementen aus dem sortierten Subarray verglichen; hier haben wir nur ein Element, A[0].
  • Wenn der Schlüssel größer als A[0] ist, fügen wir ihn hinter A[0] ein.
  • Wenn er kleiner ist, vergleichen wir erneut, um ihn an der richtigen Position vor A[0] einzufügen. (Im Falle von A[0] gibt es nur eine Position)
  • Nehmen Sie das nächste Element A[2] als Schlüssel. Vergleichen Sie es mit sortierten Subarray-Elementen und fügen Sie nach dem Element ein, das gerade kleiner als A[2] ist. Wenn es keine kleinen Elemente gibt, dann füge es am Anfang des sortierten Subarrays ein.
  • Wiederholen Sie die obigen Schritte für alle Elemente im unsortierten Subarray.

Beispiel für Einfügungssortierung

Angenommen, wir haben das Array: (5,3,4,2,1). Wir sortieren es mit dem Algorithmus der Einfügesortierung.

Sortiertes Unterarray Unsortiertes Subarray Array
( 5 ) ( 3, 4, 2, 1) (5, 3, 4, 2, 1)
  • Erste Iteration

Schlüssel : A[1] = 3

Sortiertes Subarray Unsortiertes Subarray Array
( 3 , 5) (4, 2, 1) (3, 5, 4, 2, 1)
  • Zweite Iteration

Schlüssel : A[2] = 4

Sortiertes Subarray Unsortiertes Subarray Array
( 3, 4, 5) (2, 1) (3, 4, 5, 2, 1)
  • Dritte Iteration

Schlüssel : A[3] = 2

Sortiertes Subarray Unsortiertes Subarray Array
( 2, 3, 4, 5) (1) (2, 3, 4, 5, 1)
  • Vierte Iteration

Schlüssel : A[4] = 1

Sortiertes Subarray Unsortiertes Subarray Array
( 1, 2, 3, 4, 5) () (1, 2, 3, 4, 5)

Implementierung des Einfügungs-Sortieralgorithmus

#include <iostream>
using namespace std;

void insertion_sort(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
      int key = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = key;
      j--;
    }
  }
}

int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  insertion_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Komplexität des Einfüge-Sortieralgorithmus

Zeitkomplexität

  • Durchschnittlicher Fall

Im Durchschnitt werden i Vergleiche im i-ten Durchgang der Einfügesortierung durchgeführt. Wenn es also n Iterationen gibt, dann kann die durchschnittliche Zeitkomplexität unten angegeben werden.

1 + 2 + 3 + ... + (n-1) = n*(n-1)/2

Die Zeitkomplexität liegt also in der Größenordnung von [Big Theta]: O(n2).

  • Schlimmster Fall

Der Worst-Case tritt ein, wenn das Array umgekehrt sortiert ist und die maximale Anzahl von Vergleichen und Vertauschungen durchgeführt werden muss.

Die Zeitkomplexität im schlimmsten Fall ist [Big O] O(n2).

  • Bester Fall

Der Best-Case tritt ein, wenn das Array bereits sortiert ist, und dann nur die äußere Schleife n-mal ausgeführt wird.

Die Zeitkomplexität im besten Fall ist [Big Omega]: O(n).

Platzkomplexität

Die Platzkomplexität für den Einfügungssortieralgorithmus ist O(n), da außer einer temporären Variablen kein zusätzlicher Speicher benötigt wird.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Verwandter Artikel - Sort Algorithm