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:
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.
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.
