Zitat von
negaH:
ich meinte sehr wohl Stabilität
und bezog mich damit auf deine Aussage. Bei Quicksort ist es enorm wichtig das die Comparefunction (Vergleichoperation) immer eine eindeutige Sortierung erzeugt. Ist dies nicht der Fall so wird zb. die QuickSort Implementierung in der
VCL (TList zb.) in einer Endloss-Schleife verenden.
Die eindeutige Vergleichoperation bezieht sich aber nur darauf das zb. nicht A > B und A <= B gleichzeitig gelten darf, oder zb. A > B und B > C und C > A.
QuickSort ist, je nach Implementierung, im Gegensatz zu anderen Verfahren, ziemlich anfällig für solche Kontradiktions in der Comparefunction, eben in-stabil !
Danm hab ich dich entweder falsch verstanden oder ne andere Vorstellung von dem Begriff "Stabilität".
*nochmal in die Wikipedia guckt*
http://de.wikipedia.org/wiki/Stabiles_Sortierverfahren
Jo, genau so, wie ichs im Kopf hatte:
Die Reihenfolge gleichwertiger Elemente wird nicht verändert. Das ist bei QuickSort aber nicht der Fall(im Normalfall jedenfalls). [wie gesagt, ich hatte die Frage falsch verstenden/nicht aufnmerksam genug gelesen]
Du bezieht Stabilität aber auf das Funktionieren des Algorithmus. Ohne eindeutige Vergleichsoperation ist (vergtleichsbasiertes) Sortieren
IMHO unmöglich ==> Fehler bei der Implementierung der Compare-Funktion. QuickSort als Algo funktioniert aber trotzdem.
Oder hab ich dich falsch verstanden?
mfg
Christian