Untere Schranke Vergleichssortierung

Jeder vergleichsbasierte Sortierer braucht im Worst Case mindestens logarithmisch viele Vergleiche relativ zu n!: der Entscheidungsbaum hat n! Blätter, seine Höhe ist also durch log2(n!) nach unten beschränkt.

Counting/Radix Sort umgehen das, indem sie mehr als Vergleiche nutzen (bei eingeschränkten Schlüsseluniversen).

Begründet, warum reine Vergleichssortierung im Worst Case nicht beliebig unter die informations-theoretische Schranke sinken kann. Öffnet die Tür zu Counting/Radix, wenn das Universum der Keys es erlaubt.

Vertiefung

Eine Vergleichssortierung kann als Entscheidungsbaum modelliert werden. Jeder Vergleich hat mögliche Ausgänge und teilt die noch möglichen Eingabereihenfolgen. Für n verschiedene Schlüssel muss der Baum mindestens n Fakultät verschiedene Reihenfolgen unterscheiden können.

Ein binärer Baum mit Höhe h besitzt höchstens 2 hoch h Blätter. Daraus folgt, dass die Höhe mindestens logarithmisch in n Fakultät wächst, was asymptotisch n mal log n entspricht. Die Aussage betrifft allgemeine Sortierer, die Informationen ausschliesslich aus Vergleichen gewinnen.

Schwierigkeitsstufen

1. Vergleiche als Verzweigungen eines Entscheidungsbaums deuten.
2. Blattzahl mit der Zahl möglicher Permutationen verbinden.
3. Erklären, warum Counting Sort nicht unter dieselbe Voraussetzung fällt.

Fallstricke

Die Schranke sagt nichts darüber, dass jeder konkrete Input gleich viele Vergleiche braucht. Sie gilt für den ungünstigsten Fall des Modells und kann durch zusätzliche Struktur der Schlüssel umgangen werden.