Kamm-Sortierung

1. Kamm-Sortieralgorithmus
2. Kamm-Sortier-Beispiel
3. Implementierung des Kamm-Sortieralgorithmus
4. Kamm-Sortieralgorithmus Komplexität

Kamm-Sortierung ist ein einfacher vergleichsbasierter Sortieralgorithmus. Er ist eine verbesserte Form von Blasensortierung. Bei Bubble Sort werden benachbarte Elemente in jedem Durchgang/Phase verglichen und Invertierungen nacheinander entfernt. Kamm-Sortierung hingegen beginnt mit einer großen Lücke und reduziert diese jedes Mal um einen Verkleinerungsfaktor von 1,3. Comb Sort kann mehrere Invertierungen mit nur einem Swap entfernen. Es basiert auf der Idee des Tötens der Schildkröten. Turtles sind die kleinen Elemente gegen Ende der Liste, die die Effizienz von Bubble Sort verringern, und das Töten dieser Elemente verbessert die Sortierleistung erheblich.

Kamm-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben. Wir nehmen den Schrumpfungsfaktor 1,3 an, weil er empirisch gesehen die besten Ergebnisse liefert.

Kamm-Sortier-Beispiel

Angenommen, wir haben das Array: (3, 5, 2, 8, 1, 7, 6, 4). Wir werden es mit dem Kamm-Sortieralgorithmus sortieren.

Initialisieren Sie gap=8 , swapped=true und SHRINK_FACTOR = 1.3.

• Der erste Durchlauf

gap = 8 / 1.3 = 6, swapped = false

• Der zweite Durchlauf

gap = 6 / 1.3 = 4, swapped = false

• Der dritte Durchlauf

gap = 4 / 1.3 = 3, swapped = false

• Der vierte Durchgang

gap = 3 / 1.3 = 2, swapped = false

• Der fünfte Durchgang

gap = 2 / 1.3 = 1, swapped = false

Wir erhalten das endgültige sortierte Array als: (1, 2, 3, 4, 5, 6, 7, 8).

Implementierung des Kamm-Sortieralgorithmus

#include <iostream>
using namespace std;

int updateGap(int gap) {
  gap = (gap * 10) / 13;
  if (gap < 1)
    return 1;
  else
    return gap;
}

void combSort(int arr[], int n) {
  int gap = n;
  bool swapped = true;
  while (gap > 1 || swapped == true) {
    gap = updateGap(gap);
    swapped = false;
    for (int i = 0; i < (n - gap); i++) {
      int temp;
      if (arr[i] > arr[i + gap]) {
        temp = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = temp;
        swapped = true;
      }
    }
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  combSort(arr, n);
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Kamm-Sortieralgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Die Zeitkomplexität liegt in der Größenordnung von [Big Theta]: O(n²/2^p), wobei p die Anzahl der Inkremente ist.

• Schlechtester Fall

Die Zeitkomplexität im ungünstigsten Fall ist [Big O]: O(n²).

• Bester Fall

Der Best-Case tritt auf, wenn das Array bereits sortiert oder fast sortiert ist. Die Zeitkomplexität im besten Fall ist [Big Omega]: O(nlogn). Das ist eine deutliche Verbesserung gegenüber der Best-Case-Zeitkomplexität von Blasensortierung.

Raumkomplexität

Die Platzkomplexität für diesen Algorithmus ist O(n), da der Kamm-Sortieralgorithmus außer temporären Variablen keinen zusätzlichen Platz benötigt.