Stabilität von Sortierverfahren (II)

Sortieren bzgl. $\le$ ist nur sinnvoll,
falls $\le$ reflexiv und transitiv ist.

Beispiel: x$\le$y, falls lowercase(x)$\le$lowercase(y).

Dann ist die Relation a $\approx$ b : = a$\le$b $\wedge$ b$\le$a
eine Äquivalenz-Relation.

Wenn $\le$ antisymmetrisch ist,
dann hat jede Äquivalenzklasse die Größe 1.

Nenne für das Beispiel die Äquivalenzklasse von "aBc".

Ein Sortierverfahren heißt stabil,
wenn für alle Ein/Ausgaben gilt:

• wenn i < j und x_i $\approx$ x_j, dann $\pi$(i) < $\pi$(j).