HoarePartitionierung

Die HoarePartitionierung ist ein Partitionierungsverfahren, das im Quicksort-Algorithmus verwendet wird. Sie wurde von C. A. R. Hoare im Jahr 1962 eingeführt. Das Verfahren teilt ein Array grob um einen Pivot-Wert in zwei Bereiche und bildet damit die Grundlage für die rekursiven Sortier-Schritte.

Das Verfahren verwendet zwei Indizes, die von den gegenüberliegenden Enden des zu sortierenden Bereichs nach innen wandern. Typischerweise wird ein Pivot-Wert gewählt, etwa A[(lo+hi)/2] oder A[lo]. i beginnt bei lo-1 und j bei hi+1. In einer Schleife wird i erhöht, solange A[i] < Pivot; j wird verringert, solange A[j] > Pivot. Wenn i >= j, endet die Partition und der Index j wird zurückgegeben. Andernfalls werden A[i] und A[j] vertauscht und der Vorgang setzt sich fort.

Nach der Partition gilt grob: Alle Elemente von lo bis j gehören zur linken Seite und sind nicht größer als Pivot, alle Elemente von j+1 bis hi gehören zur rechten Seite und sind nicht kleiner als Pivot. Der Pivot muss nicht zwingend seine endgültige Position einnehmen. Die nächste Stufe des Quicksort sortiert die Teilbereiche [lo..j] und [j+1..hi].

Die Zeitkomplexität beträgt im Durchschnitt O(n log n); im schlechtesten Fall kann sie O(n^2) erreichen, insbesondere bei ungünstigen Pivot-Wahlen. Der Platzbedarf ist in der typischen rekursiven Implementierung durch den Aufrufstapel auf O(log n) beschränkt.

Im Vergleich zur Lomuto-Partitionierung erfordert die Hoare-Version meist weniger Vertauschungen und arbeitet robust bei vielen Datensätzen. Sie ist jedoch feiner abgestimmt in der Implementierung, da der zurückgegebene Index nicht notwendigerweise die exakte Pivot-Position markiert.