Quicksort

1. Quicksort-Algorithmus
2. Quick-Sort-Beispiel
3. Implementierung des Quick-Sort-Algorithmus
4. Quick-Sort-Algorithmus Komplexität

Die Quicksort ist ein hocheffizienter Sortieralgorithmus, der auf dem Prinzip des Divide-and-Conquer-Algorithmus basiert. Quick Sort arbeitet, indem es das Array in zwei Teile um ein ausgewähltes Pivot-Element herum partitioniert. Es verschiebt kleinere Elemente auf die linke Seite des Pivots und größere Elemente auf die rechte Seite. Danach werden die linken und rechten Teilbereiche rekursiv sortiert, um das gesamte Array zu sortieren. Es wird Quick sort genannt, weil es etwa 2 oder 3 mal schneller ist als herkömmliche Sortieralgorithmen. Quick Sort wird häufig für die Informationssuche und numerische Berechnungen innerhalb von Datenstrukturen verwendet.

Quicksort-Algorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben. Nehmen Sie zwei Variablen, beg & end, und speichern Sie den Index des Anfangs- und des Endelements.

Partition()

QuickSort()

Quick-Sort-Beispiel

Angenommen, wir haben das Array: (6,5,1,4,2,3). Wir werden es mit dem Quick-Sort-Algorithmus sortieren.

Implementierung des Quick-Sort-Algorithmus

#include <bits/stdc++.h>
using namespace std;

int partition(int arr[], int beg, int end) {
  // Select the last element as pivot element
  int pivot = arr[end];
  int i = (beg - 1);
  // Move smaller elements to left side and larger on right side
  for (int j = beg; j < end; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1],
       arr[end]);  // Move pivot element to its right position in array
  return (i + 1);
}

void quickSort(int arr[], int beg, int end) {
  if (beg < end) {
    int pi = partition(arr, beg, end);
    quickSort(arr, beg,
              pi - 1);  // Recursive Sort element on left side of partition
    quickSort(arr, pi + 1,
              end);  // Recursive Sort element on right side of partition
  }
}
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";
  quickSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Quick-Sort-Algorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Die von Quick Sort benötigte Zeit ist durch die folgende Rekursionsbeziehung gegeben:

 T(n) = T(k) + T(n-k-1) + θ(n)

k steht hier für die Anzahl der Elemente, die kleiner/größer als das Pivot-Element sind.

Das Ergebnis dieser Rekursionsrelation ist T(n) = nLogn.Der Durchschnittsfall tritt auf, wenn wir zufällige, ungleichmäßige Partitionen erhalten. Die Zeitkomplexität liegt in der Größenordnung von [Big Theta]: O(nLogn).

• Schlimmster Fall

T(n) = T(n-1) + θ(n)

Der Worst-Case tritt auf, wenn das Pivot-Element immer entweder das größte oder das kleinste Element des Arrays ist. In diesem Fall fallen alle Elemente in ein Subarray und es müssen maximal n Aufrufe gemacht werden. Die Zeitkomplexität im schlimmsten Fall ist [Big O]: O(n²).

• Bester Fall

 T(n) = 2T(n/2) + θ(n)

Der beste Fall tritt ein, wenn das ausgewählte Pivotelement immer das mittlere Element ist oder wenn beide Partitionen gleichmäßig ausgeglichen sind, d.h. der Größenunterschied ist 1 oder weniger. Die Zeitkomplexität im besten Fall ist [Big Omega]: O(nLogn).

Raumkomplexität

Die durchschnittliche Platzkomplexität für den Schnellsortieralgorithmus ist O(Logn). Das ist der Platz, den der Rekursionsstapel benötigt. Aber im schlimmsten Fall, wenn das Sortieren eines Arrays n Rekursionen erfordert, ist die Platzkomplexität O(n).