Quicksort

• nutzt das Prinzip "divide-and-conquer"

!introprog-v10-sortieren-teil2, p.7

Komplexität

• Wenn es gelingt, die Teilfolgen durch das Gruppieren jeweils zu halbieren, erhalten wir eine Komplexität von: $T_{bc}=O(n\log n)$
  • $T_{bc}$ bedeutet best case
• Wird jeweils nur eine Teilfolge konstanter Länge abgespalten, so wird n mal gruppiert und daher: $T_{wc}=O(n^2)$
  • $T_{wc}$ bedeutet worst case
• Im Durchschnitt ist allerdings die Länge der Intervalle abhängig von n und man braucht nur zweimal mehr Operationen als im besten Fall: $T_{ac}=O(n\log n)$
  • $T_{ac}$ bedeutet average case

Varianten

• Vorgeschlagene Varianten betreffen die Wahl des Trennwerts für das Gruppieren, der in der vorliegenden Form für das schlechte Verhalten bei nahezu sortierten Folgen verantwortlich ist:
  1. Trennindex zufällig aus [start, end]
  2. Trennwert als Median aus drei Elementen $\{f_{\text{start}},f|\frac{\text{start}+\text{end}}{2}|,f_{\text{end}}\}$
• Beide Varianten haben sich gut bewährt und sorgen auch bei fast sortierten Folgen für O(n log n).
• Es ist außerdem vorteilhaft, die kleinere Teilfolge zuerst zu sortieren (Rekursionstiefe minimieren)

Quick Sort mit Listen

• Zerlegen einer Folge in zwei Teilfolgen, wovon die eine die kleineren (<) Elemente, die andere die größeren (≥) Elemente enthält
  • Als Trennwert (pivot) wird oft der Wert des ersten Elements genommen.
  • Statt des Vertauschens (swap) werden die Elemente in zwei neue Listen (left, right) versetzt (move).
  • Diese werden dann rekursiv sortiert und zu der Resultatliste zusammengesetzt.
  • Die Komplexität des Gruppierungsverfahrens ist, wie bei den Arrays, O(n), da die Liste genau einmal abgelaufen wird und jeweils konstanter Aufwand entsteht

Beispiele

Beispiel 1 (aus Vorlesung)

• vor Gruppieren
  !introprog-v10-sortieren-teil2, p.11
• Partition
  !introprog-v10-sortieren-teil2, p.13
  !introprog-v10-sortieren-teil2, p.14
• Quicksort
  !introprog-v10-sortieren-teil2, p.16
  !introprog-v10-sortieren-teil2, p.17
  !introprog-v10-sortieren-teil2, p.18
  !introprog-v10-sortieren-teil2, p.19

Beispiel 2 (Wikipedia)

• Beispiel an einem Array
  !300
  - Quicksort mit Array
  - Pivot: letztes Element (dunkler Hintergrund)
  - Arrays werden von links nach rechts abgearbeitet
  - Statt linker und rechter Liste: Ringtausch

Stabilität

Quicksort ist nur dann stabil, wenn alle Elemente mit dem gleichen Wert des gewählten Pivots, die vor bzw. nach dem Pivot kommen, auch entsprechend in die linke bzw. rechte Liste gehen.

Pseudocode

Quick Sort in C

// C program to implement Quick Sort Algorithm
#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {

    // Initialize pivot to be the first element
    int p = arr[low];
    int i = low;
    int j = high;

    while (i < j) {

        // Find the first element greater than
        // the pivot (from starting)
        while (arr[i] <= p && i <= high - 1) {
            i++;
        }

        // Find the first element smaller than
        // the pivot (from last)
        while (arr[j] > p && j >= low + 1) {
            j--;
        }
        if (i < j) {
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[low], &arr[j]);
    return j;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {

        // call partition function to find Partition Index
        int pi = partition(arr, low, high);

        // Recursively call quickSort() for left and right
        // half based on Partition Index
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
  
    int arr[] = { 4, 2, 5, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    // calling quickSort() to sort the given array
    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}