Sortierergebnis

Zuvörderst sei hier natürlich die Sortiertheit der Menge (jeder Nachfolger ist nicht kleiner als sein Vorgänger) zu nennen, das ist trivial. Bei stabilen Sortieralgorithmen müssen alle gleich(schlüsselig)en Elemente zudem in der Ausgangsreihenfolge vorliegen, sonst ist er instabil.

Doch die sortierte Menge birgt darüberhinaus noch eine Überraschung (was ich ebenfalls nirgendwo erwähnt fand): Ihre „sichtbare Oberkante“ ist der (an der Diagonale links unten nach rechts oben gespiegelte) Graph der (kumulierten / kumulativen) Verteilungsfunktion der Wahrscheinlichkeitsverteilung ihrer Elemente. Das soll erläutert werden. Zunächst der einfachste Fall, eine stetig gleichverteilte Startmenge, bei der alle Elemente(größen) gleich wahrscheinlich sind:

Nach Sortierung derselben ergibt sich eine sortierte Menge mit nahezu linearer Oberkante:


Eine Spiegelung an der eingangs genannten Diagonale ändert diese Linie nicht, sodaß diese sortierte Menge bereits den Graphen ihrer Verteilungsfunktion repräsentiert.

Der nächstkomplizierte Fall: Addiert man die jeweiligen Zufallswerte zweier Gleichverteilungen (man „faltet“ diese Verteilungen), ergibt sich eine sog. Dreiecksverteilung:

Hier ist bereits deutlich zu sehen, daß sich die Werte stärker auf halber Höhe als bei der Gleichverteilung drängen. Dreiecksverteilt wird diese Verteilung deshalb genannt, weil der Graph der Wahrscheinlichkeitsdichtefunktion ein (symmetrisches bzw. gleichschenkliges) Dreieck ist. Man kann sich das so vorstellen, daß die mittelgroßen Werte die am häufigsten bzw. wahrscheinlichsten auftretenden sind, und, je mehr die Werte nach unten und oben von dem am wahrscheinlichsten / häufigsten auftretenden Wert abweichen, immer unwahrscheinlicher werden. Der Abfall der Wahrscheinlichkeiten ist beidseitig linear, sodaß der Graph der gesamten Dichtefunktion dreiecksförmig verläuft. Sortiert man nun auch diese Startmenge:

ist die Oberkante der sortierten Menge nicht mehr linear. Spiegelt man an der genannten Diagonale (oder wendet äquivalente Operationen/Transformationen an):


liegt nunmehr der Graph der Verteilungsfunktion einer dreiecksverteilten Startmenge bzw. Zufallsgröße/-funktion vor.  Da die kleinen und großen Elemente die seltensten sind, ist dort der Anstieg des Graphen am geringsten (flachesten), währendhingegen bei den am häufigsten auftretenden, den mittelgroßen Elementen, der Anstieg am stärksten (steilsten) ist.

Kontaktformular