Quicksort

Zweipunktnull

Commander
Registriert
Dez. 2004
Beiträge
2.546
Hallo, ich hab mal eine Frage zum Quicksort, genauer zur Teilfunktion "teilen", "partitionieren" oder wie man sie auch nennen will. Ich poste einfach mal eine Beispiel-partitionieren-Funktion:

Code:
procedure partitioniere(int[] Array, int L, int R) 
    L0 := L
    // Wählt als PivotElement Array[L0].  Dies ist für praktische
    // Anwendungen SCHLECHT
    while L < R
[B]	  if Array[R] > Array[L0]   [/B]
	      R := R - 1
[B]	  elseif Array[L] <= Array[L0][/B]
	      L := L + 1
          else
	      swap(Array, L, R)
          endif
    endwhile
    swap(Array, L0, R)  // vertausche mit dem Pivot
endprocedure

Die wichtigen Stellen habe ich fett dargestellt. Bei allen möglichen Quellen findet man dort > und <= oder halt >= und <. Jedoch ist es doch ebenso möglich, >= und <= bzw. <= und >= zu verwenden? Ich überlege schon über ne Stunde nach irgendeinem Fall, in dem diese Lösung nicht funktionieren würde und jetzt will ich es sicher wissen. :) Oder gibts Gründe, wieso man nur bei einem ein Gleichheitszeichen drin haben sollte? Eigentlich ist das doch eher unpraktisch, weil dann mehr Elemente vertauscht werden müssen.
 
Wenn man größergleich/kleinergleich bei beiden Abfragen macht wird ein Element nicht miterfasst?

Siehe auch: Off-by-one Bug.
 
>> Wenn man größergleich/kleinergleich bei beiden Abfragen macht wird ein Element nicht miterfasst?

Ja, alle Elemente, die denselben Wert wie das Pivotelement haben, werden dann nicht sortiert. Das ist aber doch egal, weil sich diese Elemente doch beliebig auf die beiden Teilmengen aufteilen können, oder?
 
Für alle Elemente die den selben Wert wie das Pivotelement haben greift dann die else Bedingung und sie werden immer getauscht.
Das ist doch unnötiger Aufwand, wenn die Endposition der Elemente, die gleich dem Pivotelement sind, egal ist, und verlangsamt das Programm.
 
Hm, also entweder hab ich n Denkfehler oder du. Im Moment ist es doch so, dass Elemente mit dem Wert des Pivotelementes teilweise vertauscht werden.

if Array[R] > Array[L0]
Angenommen, Array[R] hat denselben Wert wie das Pivotelement. Dann würde bei der Bedingung Array[R] > Array[L0] der Else-Zweig (also die Vertauschung!) greifen. Bei > werden also unsinnigerweise Elemente mit dem Wert des Pivotelementes vertauscht, obwohl dies nicht nötig sein müsst, da sich diese ja in beiden Teilmengen aufhalten dürfen.

Meine Idee war es, anstatt > einfach >= zu nehmen. Bei der Bedingung Array[R] >= Array[L0] würde der Else-Zweig (also die Vertauschung) nämlich wirklich nur greifen, wenn das Element kleiner als das Pivotelement ist. Wenn das gleich dem Pivotelement ist, wird es stehen gelassen, was doch gut ist, oder nicht?
 
Achso. Shit. Ich hatte gelesen, dass du nur < und > benutzen wolltest.
Wenn du <= und >= benutzt, schließt du Bedingungen mit ein, die beim elseif gar nicht
mehr auftreten können, weil die gleichgroßen schon beim ersten <= erfasst sind.
Also würde ich beim if <= und beim elseif > benutzen. So muss bei gleichgroßen
Elementen die elseif Bedingung gar nicht mehr geprüft werden.
 
>> Wenn du <= und >= benutzt, schließt du Bedingungen mit ein, die beim elseif gar nicht mehr auftreten können

Hm, nein, wieso das denn?

if Array[R] >= Array[L0]
R := R - 1
Diese Code repräsentiert doch sozusagen einen Zeiger, der beim rechten Element anfängt und von da aus nach links geht, bis er auf ein Element trifft, welches kleiner als das Pivotelement ist.

elseif Array[L] <= Array[L0]
L := L + 1
Diese Code repräsentiert einen Zeiger, der beim linken Element anfängt und von da aus nach rechts geht, bis er auf ein Element trifft, welches größer als das Pivotelement ist.

Vondaher muss man doch >= und <= nehmen, weil andernfalls einer der beiden Zeiger bereits bei einem Element "hängen bleibt", welches lediglich gleich dem Pivotelement ist. Oder liegt ich da falsch?
 
Zuletzt bearbeitet:
Zurück
Oben