Quicksort-Partitionierung: Hoare vs. Lomuto

82

Es gibt zwei QuickSort-Partitionsmethoden, die in Cormen erwähnt werden:

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

und:

Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i +1], A[r] )
return i + 1

In welchen Situationen ist das eine dem anderen vorzuziehen, wenn man die Methode zur Auswahl des Pivots außer Acht lässt? Ich weiß zum Beispiel, dass Lomuto relativ schlecht vorformt, wenn es einen hohen Prozentsatz an doppelten Werten gibt (dh wenn das Array beispielsweise mehr als 2/3 desselben Werts hat), wobei Hoare in dieser Situation eine gute Leistung erbringt.

Welche anderen Sonderfälle machen eine Partitionsmethode signifikant besser als die andere?

Robert S. Barnes
quelle
2
Ich kann mir keine Situation vorstellen, in der Lomuto besser ist als Hoare. Es scheint, als würde Lomuto jedes Mal zusätzliche Swaps durchführen A[i+1] <= x. In einem sortierten Array (und bei vernünftigerweise gewählten Pivots) macht Hoare fast keine Swaps und Lomuto macht eine Tonne (sobald j klein genug ist, dann alle A[j] <= x.) Was vermisse ich?
Wandering Logic
2
@WanderingLogic Ich bin mir nicht sicher, aber es scheint, dass Cormens Entscheidung, die Lomuto-Partition in seinem Buch zu verwenden, pädagogisch sein könnte - es scheint eine ziemlich direkte Schleifeninvariante zu haben.
Robert S. Barnes
2
Beachten Sie, dass diese beiden Algorithmen nicht dasselbe tun. Am Ende von Hoares Algorithmus befindet sich der Drehpunkt nicht am endgültigen Platz. Sie können ein swap(A[p], A[j])am Ende von Hoare hinzufügen , um dasselbe Verhalten für beide zu erhalten.
Aurélien Ooms
Sie sollten auch i < jin den 2 Wiederholungsschleifen der Hoare-Partitionierung nachsehen.
Aurélien Ooms
@ AurélienOoms Der Code wird direkt aus dem Buch kopiert.
Robert S. Barnes

Antworten:

92

Pädagogische Dimension

Aufgrund seiner Einfachheit ist die Partitionierungsmethode von Lomuto möglicherweise einfacher zu implementieren. Es gibt eine nette Anekdote in Jon Bentleys Programmierperle über das Sortieren:

„Die meisten Diskussionen über Quicksort verwenden ein Partitionierungsschema, das auf zwei sich nähernden Indizes basiert [...] [dh Hoares]. Obwohl die Grundidee dieses Schemas einfach ist, habe ich die Details immer als schwierig empfunden - ich habe einmal den größten Teil von zwei Tagen damit verbracht, einen Fehler in einer kurzen Partitionierungsschleife aufzuspüren. Ein Leser eines Vorentwurfs beklagte sich darüber, dass die Standardmethode mit zwei Indizes tatsächlich einfacher als die von Lomuto sei, und skizzierte einen Code, um dies zu verdeutlichen. Ich habe aufgehört zu suchen, nachdem ich zwei Bugs gefunden habe. “

Leistungsdimension

Für den praktischen Gebrauch kann die einfache Implementierung aus Gründen der Effizienz geopfert werden. Auf theoretischer Basis können wir die Anzahl der Elementvergleiche und Swaps bestimmen, um die Leistung zu vergleichen. Darüber hinaus wird die tatsächliche Laufzeit von anderen Faktoren beeinflusst, wie z. B. der Caching-Leistung und falschen Vorhersagen für Zweige.

Wie unten gezeigt, verhalten sich die Algorithmen bei zufälligen Permutationen mit Ausnahme der Anzahl der Swaps sehr ähnlich . Dort braucht Lomuto dreimal so viele wie Hoare!

Anzahl der Vergleiche

n1n

Anzahl der Swaps

Die Anzahl der Auslagerungen ist für beide Algorithmen abhängig von den Elementen im Array zufällig. Wenn wir zufällige Permutationen annehmen , dh alle Elemente sind unterschiedlich und jede Permutation der Elemente ist gleich wahrscheinlich, können wir die erwartete Anzahl von Swaps analysieren .

1,,n

Lomutos Methode

jA[j]x1,,nx1xx1x

{1,,n}1n

1nx=1n(x1)=n212.

n

Hoares Methode

x

ijxij

x

Hyp(n1,nx,x1)nxx1(nx)(x1)/(n1)x

Abschließend werden alle Pivot-Werte erneut gemittelt, um die insgesamt erwartete Anzahl von Swaps für die Hoare-Partitionierung zu erhalten:

1nx=1n(nx)(x1)n1=n613.

(Eine genauere Beschreibung finden Sie in meiner Masterarbeit , Seite 29.)

Speicherzugriffsmuster

Beide Algorithmen verwenden zwei Zeiger in das Array, die es nacheinander abtasten . Daher verhalten sich beide nahezu optimal bezüglich Caching.

Gleiche Elemente und bereits sortierte Listen

Wie bereits von Wandering Logic erwähnt, unterscheidet sich die Leistung der Algorithmen bei Listen, die keine zufälligen Permutationen sind, drastischer.

n/2

0ijO(nlogn)

0A[j] <= xi=nΘ(n2)

Fazit

Die Methode von Lomuto ist einfach und einfacher zu implementieren, sollte jedoch nicht für die Implementierung einer Bibliotheksortierungsmethode verwendet werden.

Sebastian
quelle
16
Wow, das ist eine ausführliche Antwort. Schön gemacht!
Raphael
Muss Raphael zustimmen, wirklich nette Antwort!
Robert S. Barnes
1
Ich möchte eine kleine Klarstellung machen, dass die Anzahl der Vergleiche, die Lomuto durchführt, mit abnehmendem Verhältnis der einzelnen Elemente zu den gesamten Elementen erheblich schneller zunimmt als die von Hoare. Dies ist wahrscheinlich auf eine schlechte Partitionierung von Lomuto und eine gute durchschnittliche Partitionierung von Hoare zurückzuführen.
Robert S. Barnes
Tolle Erklärung der beiden Methoden! Danke!
V Kouk
Sie können leicht eine Variante der Lomuto-Methode erstellen, die alle Elemente extrahiert, die dem Drehpunkt entsprechen, und sie aus der Rekursion herauslässt, obwohl ich nicht sicher bin, ob dies den Durchschnittsfall unterstützen oder behindern würde.
Jakub Narębski
5

Einige Kommentare ergänzten die ausgezeichnete Antwort von Sebastian.

Ich werde über den Algorithmus zur Partitionsumlagerung im Allgemeinen sprechen und nicht über seine besondere Verwendung für Quicksort .

Stabilität

Der Algorithmus von Lomuto ist semistabil : Die relative Reihenfolge der Elemente, die das Prädikat nicht erfüllen, bleibt erhalten. Hoares Algorithmus ist instabil.

Elementzugriffsmuster

Der Algorithmus von Lomuto kann mit einfach verknüpften Listen oder ähnlichen Nur-Vorwärts-Datenstrukturen verwendet werden. Der Hoare-Algorithmus benötigt Bidirektionalität .

Anzahl der Vergleiche

n1n

Dafür müssen wir aber 2 Eigenschaften opfern:

  1. Die zu partitionierende Sequenz darf nicht leer sein.
  2. Der Algorithmus kann den Partitionspunkt nicht zurückgeben.

n

Fernando Pelliccioni
quelle