Einfügung Sortierung

1. Einfüge-Sortieralgorithmus
2. Beispiel für Einfügungssortierung
3. Implementierung des Einfügungs-Sortieralgorithmus
4. Komplexität des Einfüge-Sortieralgorithmus

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.

Beispiel für Einfügungssortierung

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

• Erste Iteration

Schlüssel : A[1] = 3

• Zweite Iteration

Schlüssel : A[2] = 4

• Dritte Iteration

Schlüssel : A[3] = 2

• Vierte Iteration

Schlüssel : A[4] = 1

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(n²).

• 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(n²).

• 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.