stabilität von sortieralgorithmen beweisen

[shisha]

wie kann ich die stabilität von sortieralgorithmen beweisen oder widerlegen?

[Blue-Tiger]

Widerlegen: such dir ein Gegenbeispiel (d.h. ein Beispielinput, der nach durchfuehren des Algo nicht stabil sortiert ist).

Beweisen: Zeig dass fuer zwei beliebige Elemente des Inputs, welche den gleichen Sortierwert haben, ihre relative Position zueinander sich nicht aendert. Ist idR. schwieriger als das Widerlegen

[testall]

Eine kleine Zusatzfrage, weil das Thema hier grad so schön passt:
Gibt es eine stabile Variante von Quicksort und wenn ja, wie beweise/widerlege ich es?

ich denke nämlich dass der folgende stabil sein dürfte:

quicksort(Feld F):=
    Wähle Vergleichsselement F[i]
    Durchlaufe alle Elemente mit Index j
        bilde 3 Teilfolgen:
            F1 : Elemente < F[i]
            F2 : Elemente gleich F[i]
            F3 : kleiner F[i]
    Sind die Anzahl der Elemente in F1/F2 ungleich 0
        quicksort(F1/F2)
end quicksort

[Jester]

Wenn Du F2 richtig zusammenbaust dann schon.