Randomisierter Quicksort

Quicksort ist einer der klassischsten Sortieralgorithmen der Informatik und bekannt für seine durchschnittliche Zeitkomplexität von O(n log n). Wenn die Eingabedaten jedoch bereits sortiert oder nahezu sortiert sind, verschlechtert sich das traditionelle Quicksort auf eine Zeitkomplexität von O(n²). Randomisiertes Quicksort löst dieses Problem clever durch die Einführung von Zufälligkeit.

Bevor wir uns eingehend mit randomisiertem Quicksort beschäftigen, wollen wir zunächst die Kernidee des traditionellen Quicksorts rekapitulieren.

Wie Quicksort funktioniert

Quicksort verwendetDivide-and-Conquer-Strategie, die grundlegenden Schritte sind wie folgt:

  1. Pivot-Wert auswählenWähle ein Element aus dem Array als Pivot-Wert.
  2. PartitionsoperationOrdne das Array so um, dass alle Elemente, die kleiner als der Pivot sind, vor ihm platziert werden und alle Elemente, die größer als der Pivot sind, nach ihm platziert werden.
  3. rekursiv sortierenWende denselben Prozess rekursiv auf die Teilarrays auf beiden Seiten des Pivots an.

Probleme mit traditionellem Quicksort

Die Leistung des traditionellen Quicksort hängt stark von der Wahl des Pivots ab. Der Algorithmus ist am effizientesten, wenn der Pivot das Array jedes Mal ungefähr in zwei gleich große Hälften teilen kann. Die Leistung verschlechtert sich jedoch erheblich in den folgenden Fällen:

  • Sortiertes ArrayWenn das Array bereits sortiert ist, führt die Wahl des letzten Elements als Pivot jedes Mal zu extrem unausgeglichenen Partitionen.
  • Array in umgekehrter ReihenfolgeÄhnlich wie ein sortiertes Array, aber in entgegengesetzter Richtung.
  • DuplikateEine große Anzahl doppelter Elemente kann ebenfalls zu unausgeglichenen Partitionen führen.

In diesen Worst-Case-Szenarien verschlechtert sich die Zeitkomplexität von Quicksort auf O(n²), vergleichbar mit einfachen Algorithmen wie Bubblesort.

Randomisierter Quicksort vermeidet Worst-Case-Szenarien durch die Einführung von Zufälligkeit, wodurch sichergestellt wird, dass der Algorithmus bei verschiedenen Eingaben eine gute durchschnittliche Leistung beibehält.

Die zentrale Verbesserung des randomisierten Quicksorts ist sehr einfach:Pivot zufällig auswählenAnstatt immer das erste, letzte oder mittlere Element zu wählen, wird ein zufälliges Element als Pivot gewählt. Diese Zufälligkeit macht die Wahrscheinlichkeit des Worst Case extrem gering und gewährleistet dadurch eine erwartete Zeitkomplexität von O(n log n).

Grundidee des randomisierten Quicksort:Durch einen einzigen Sortierdurchlauf werden die zu sortierenden Daten in zwei unabhängige Teile geteilt, wobei alle Daten im einen Teil kleiner sind als alle Daten im anderen Teil. Dann wird Quicksort rekursiv auf jeden dieser beiden Teile angewendet. Der gesamte Sortiervorgang kann rekursiv ablaufen, wodurch die gesamten Daten in eine geordnete Reihenfolge gebracht werden.

Vorteile des Algorithmus

Funktionen Traditioneller Quicksort Randomisierter Quicksort
Zeitkomplexität im schlechtesten Fall O(n²) O(n²) (aber mit extrem geringer Wahrscheinlichkeit)
Durchschnittliche Zeitkomplexität O(n log n) O(n log n)
Bedingungen für den Worst Case Spezifische Eingaben (wie bereits sortierte Arrays) Die zufällige Auswahl wählt zufällig immer den Extremwert
Speicherkomplexität O(log n) (rekursiver Stack) O(log n) (rekursiver Stack)
Stabilität instabil instabil

Obwohl die Zeitkomplexität des randomisierten Quicksorts im Worst Case theoretisch immer noch O(n²) beträgt, ist die Wahrscheinlichkeit, dass dieser Worst Case eintritt, in der Praxis extrem gering. Für ein Array mit n Elementen beträgt die Wahrscheinlichkeit, dass die zufällige Pivot-Auswahl zum Worst Case führt, ungefähr 1/n!, was in der Praxis nahezu unmöglich ist.

Prozessdiagramm

In einem Array wird ein Pivot ausgewählt, zum Beispiel die 4 an der ersten Position; dann wird die 4 an ihre korrekte Position verschoben, sodass die Daten im vorhergehenden Teilarray kleiner als 4 und die Daten im nachfolgenden Teilarray größer als 4 sind, und dann wird rekursiv fortgefahren, bis die gesamte Sortierung abgeschlossen ist.

Das Verschieben der ausgewählten Pivot-Daten an ihre korrekte Position ist der Kern von Quicksort, und wir nennen diesen Vorgang Partition.

Der Prozess ist wie folgt, wobeiidie Position des Elements ist, das gerade durchlaufen und verglichen wird:

Dieser Partitionierungsprozess wird im Code wie folgt ausgedrückt:

Beispiel

    ...
private static int partition(Comparable[] arr, int l, int r){
    Comparable v = arr[l];

    int j = l;
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i].compareTo(v) < 0 ){
            j ++;
            // Positionen der Array-Elemente vertauschen
            swap(arr, j, i);
        }

    swap(arr, l, j);

    return j;
}
   ...

Wenn Quicksort auf ein nahezu sortiertes Array angewendet wird, sind die Teilarrays nach jeder Partition extrem unausgeglichen, und es kann leicht zuO(n^2)einem Algorithmus mit Zeitkomplexität degenerieren. Wir müssen den obigen Code optimieren, indem wir ein Pivot als Vergleichsbasis zufällig auswählen, was als randomisierter Quicksort-Algorithmus bezeichnet wird. Wir müssen nur die folgende Zeile vor dem obigen Code hinzufügen, um ein Element im Array zufällig auszuwählen und es mit den Pivot-Daten zu vertauschen.

swap( arr, l , (int)(Math.random()*(r-l+1))+l );

Java-Beispielcode

Quellcode-Paket-Download:Herunterladen

Code der Datei QuickSort.java:

package example;

/**
* Randomisierter Quicksort
 */
public class QuickSort {


    // Partitionierungsoperation auf dem Teil arr[l...r] ausführen
    // Gib p zurück, sodass arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    private static int partition(Comparable[] arr, int l, int r){

        // Zufällig einen Wert als Pivot im Bereich arr[l...r] auswählen
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );
        Comparable v = arr[l];
        // arr[l+1...j] < v ; arr[j+1...i) > v
        int j = l;
        for( int i = l + 1 ; i <= r ; i ++ )
            if( arr[i].compareTo(v) < 0 ){
                j ++;
                swap(arr, j, i);
            }
        swap(arr, l, j);
        return j;
    }

    // Quicksort rekursiv verwenden, um den Bereich arr[l...r] zu sortieren
    private static void sort(Comparable[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){
        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // QuickSort testen
    public static void main(String[] args) {

        // Quick Sort ist ebenfalls ein Algorithmus mit O(n log n)-Komplexität
        // Kann Daten in der Größenordnung von 1 Million problemlos innerhalb von 1 Sekunde verarbeiten
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        SortTestHelper.printArray(arr);

    }
}

Implementierung von randomisiertem Quicksort

Python-Implementierung

Beispiel

import random

def randomized_quick_sort(arr, low=None, high=Keine):
    """
Hauptfunktion für randomisierten Quicksort
   
Parameter:
arr: die zu sortierende Liste
low: Startindex des Teilarrays (Standard: 0)
high: Endindex des Teilarrays (Standard: len(arr)-1)
   
Rückgabe:
Die sortierte Liste (in-place sortiert; gibt auch die sortierte Liste zurück)
    """
    # Standardparameter setzen
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
   
    # Abbruchbedingung der Rekursion: Die Länge des Teilarrays ist kleiner oder gleich 1
    if low < high:
        # Pivot zufällig auswählen und partitionieren
        pivot_index = randomized_partition(arr, low, high)
       
        # Linke und rechte Teilarrays rekursiv sortieren
        randomized_quick_sort(arr, low, pivot_index - 1)
        randomized_quick_sort(arr, pivot_index + 1, high)
   
    return arr

def randomized_partition(arr, low, high):
    """
Randomisierte Partitionierungsfunktion
   
Parameter:
arr: die zu partitionierende Liste
low: Startindex des Teilarrays
high: Endindex des Teilarrays
   
Rückgabe:
Der endgültige Positionsindex des Pivot-Werts
    """
    # Wähle zufällig einen Index als Pivot-Position aus
    random_index = random.randint(low, high)
   
    # Tausche das zufällig ausgewählte Element mit dem letzten Element
    arr[random_index], arr[high] = arr[high], arr[random_index]
   
    # Verwende das letzte Element (das nun das zufällig ausgewählte Element ist) als Pivot
    return partition(arr, low, high)

def partition(arr, low, high):
    """
Partitionsfunktion (wie bei Quicksort)
   
Parameter:
arr: die zu partitionierende Liste
low: Startindex des Teilarrays
high: Endindex des Teilarrays
   
Rückgabe:
Der endgültige Positionsindex des Pivot-Werts
    """
    pivot = arr[high]  # Pivot
    i = low - 1        # Grenze des Bereichs, der kleiner als der Pivot ist
   
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            # Elemente vertauschen
            arr[i], arr[j] = arr[j], arr[i]
   
    # Setze das Pivot an die richtige Position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Testdaten
test_data = [3, 6, 8, 10, 1, 2, 1]
print("Ursprüngliches Array:", test_data)
print("Sortiertes Array:", randomized_quick_sort(test_data.copy()))

Zeitkomplexitätsanalyse

Die Zeitkomplexität des randomisierten Quicksorts kann durch die folgende Formel ausgedrückt werden:

\[ T(n) = O(n) + T(k) + T(n - k - 1) \]

Wobei:

  • \( O(n) \) ist die Zeit für die Partitionierungsoperation.
  • \( T(k) \) ist die Zeit zum Sortieren des linken Teilarrays.
  • \( T(n - k - 1) \) ist die Zeit zum Sortieren des rechten Teilarrays.
  • \( k \) ist die Anzahl der Elemente links vom Pivot-Wert.

In der randomisierten Version ist der Erwartungswert von \( k \) gleich \( n/2 \), daher ist die erwartete Zeitkomplexität:

\[ E[T(n)] = O(n \log n) \]

Varianten und Optimierungen des randomisierten Quicksort

1. Drei-Wege-Quicksort

Wenn das Array viele doppelte Elemente enthält, ist traditioneller Zwei-Wege-Quicksort nicht effizient. Drei-Wege-Quicksort teilt das Array in drei Teile: kleiner als das Pivot-Element, gleich dem Pivot-Element und größer als das Pivot-Element.

Beispiel

def randomized_three_way_quick_sort(arr, low=None, high=Keine):
    """Drei-Wege-randomisierter Quicksort"""
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
   
    if low < high:
        # Pivot zufällig auswählen
        random_index = random.randint(low, high)
        arr[random_index], arr[low] = arr[low], arr[random_index]
        pivot = arr[low]
       
        # Drei-Wege-Partition
        lt = low      # Bereichsgrenze für Werte kleiner als das Pivot
        gt = high     # Bereichsgrenze für Werte größer als das Pivot
        i = low + 1   # Aktuell geprüftes Element
       
        while i <= gt:
            if arr[i] < pivot:
                arr[lt], arr[i] = arr[i], arr[lt]
                lt += 1
                i += 1
            elif arr[i] > pivot:
                arr[i], arr[gt] = arr[gt], arr[i]
                gt -= 1
            else:
                i += 1
       
        # Partitionen kleiner und größer als das Pivot rekursiv sortieren
        randomized_three_way_quick_sort(arr, low, lt - 1)
        randomized_three_way_quick_sort(arr, gt + 1, high)
   
    return arr

# Test mit Daten, die Duplikate enthalten
test_data_with_duplicates = [3, 6, 3, 8, 1, 3, 6, 1]
print("Original-Array (mit Duplikaten):", test_data_with_duplicates)
print("Nach Drei-Wege-Quicksort:", randomized_three_way_quick_sort(test_data_with_duplicates.copy()))

2. Optimierung für kleine Arrays

Für sehr kleine Arrays (typischerweise weniger als 10-20 Elemente) kann Insertion Sort effizienter sein als Quicksort. Wir können die Vorteile der beiden Algorithmen kombinieren:

Beispiel

def optimized_randomized_quick_sort(arr, low=None, high=None, threshold=10):
    """Optimierter randomisierter Quicksort: Insertion Sort für kleine Arrays verwenden"""
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
   
    # Insertion Sort für kleine Arrays verwenden
    if high - low + 1 <= threshold:
        insertion_sort(arr, low, high)
        return arr
   
    if low < high:
        pivot_index = randomized_partition(arr, low, high)
        optimized_randomized_quick_sort(arr, low, pivot_index - 1, threshold)
        optimized_randomized_quick_sort(arr, pivot_index + 1, high, threshold)
   
    return arr

def insertion_sort(arr, low, high):
    """Insertion Sort, wird zum Sortieren kleiner Arrays verwendet"""
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Testen der Optimierung für kleine Arrays
small_test_data = [9, 3, 7, 1, 5, 2, 8, 4, 6]
print("Ursprüngliches kleines Array:", small_test_data)
print("Nach optimierter Sortierung:", optimized_randomized_quick_sort(small_test_data.copy(), threshold=5))

Leistungsvergleich und praktische Empfehlungen

Leistungstest

Lassen Sie uns die Leistung verschiedener Sortieralgorithmen anhand praktischer Tests vergleichen.

Beispiel

import time
import random as rand

def performance_test():
    """Leistungstest: Ausführungszeiten verschiedener Sortieralgorithmen vergleichen"""
    algorithms = {
        "Randomisierter Quicksort": randomized_quick_sort,
        "Drei-Wege-Quicksort": randomized_three_way_quick_sort,
        "Optimierter Quicksort": optimized_randomized_quick_sort,
    }
   
    # Testdaten generieren
    test_sizes = [100, 1000, 10000]
   
    for size in test_sizes:
        print(f"\nTest-Arraygröße: {size}")
       
        # Verschiedene Arten von Testdaten generieren
        test_cases = {
            "Zufällige Daten": [rand.randint(0, 10000) for _ in range(size)],
            "Sortierte Daten": list(range(size)),
            "Umgekehrte Daten": list(range(size, 0, -1)),
            Große Menge doppelter Daten: [rand.randint(0, 10) for _ in range(size)],
        }
       
        for case_name, test_data in test_cases.items():
            print(f" {case_name}:")
           
            for algo_name, algo_func in algorithms.items():
                data_copy = test_data.copy()
                start_time = time.time()
                algo_func(data_copy)
                end_time = time.time()
               
                execution_time = (end_time - start_time) * 1000  # In Millisekunden umrechnen
                print(f" {algo_name}: {execution_time:.2f} ms")

# Leistungstest ausführen (Hinweis: Dies kann bei großen Arrays einige Zeit dauern)
# performance_test()

Mehr Codebeispiele

Weitere Erweiterungen