Es seien n verschiedene Zahlen zu sortieren. Jedes Sortierverfahren muss die n! Permutationen dieser n Zahlen voneinander unterscheiden können, da es sie unterschiedlich behandeln muss, um sie zu sortieren.
Die Anzahl der Ja/Nein-Entscheidungen, die notwendig sind, um die unterschiedlichen Permutationen voneinander zu unterscheiden, ist eine untere Schranke für die Komplexität von Sortierverfahren. Diese untere Schranke wird informationstheoretische untere Schranke genannt. Nach der Informationstheorie beträgt die Anzahl der Ja/Nein-Entscheidungen für die Unterscheidung von n! verschiedenen Fällen log2(n!).
Es ist leicht zu sehen, dass gilt:
n! ≥ (n/2)n/2.
Somit gilt:
| log(n!) | ≥ log((n/2)n/2) | |
| = n/2 · log(n/2) | ||
| ∈ Ω(n log(n)). |
Jedes Sortierverfahren, das auf Vergleichen beruht, bezieht seine Information ausschließlich aus Ja/Nein-Entscheidungen, nämlich ob die jeweils verglichenen Zahlen in richtiger oder falscher Reihenfolge stehen. Jedes solche Sortierverfahren benötigt also mindestens proportional zu n log(n) viele Vergleiche, hat somit also eine Komplexität von Ω(n log(n)).
Die Sortierverfahren Heapsort und Mergesort benötigen auch höchstens proportional zu n log(n) viele Schritte. Diese beiden Verfahren sind also optimal, da sie die untere Schranke erreichen.
Alle Sortierverfahren, die wir bisher kennen gelernt haben, beruhen auf Vergleichen. Die im Folgenden kurz dargestellten Verfahren Bucket Sort und Radix Sort beziehen pro Schritt mehr Information, als ein Vergleich liefert. Für diese Verfahren ist die informationstheoretische untere Schranke daher nicht zugleich eine untere Schranke für die Anzahl der Schritte.
Weiter mit: [Bucket Sort und Radix Sort] oder [up]