Sortier­verfahren Untere Schranken für das Sortieren

Es seien n verschiedene Zahlen zu sortieren. Jedes Sortier­verfahren muss die n! Per­mutationen dieser n Zahlen voneinander unterscheiden können, da es sie unter­schiedlich behandeln muss, um sie zu sortieren.

Die Anzahl der Ja/Nein-Entscheidungen, die notwendig sind, um die unter­schiedlichen Per­mutationen voneinander zu unterscheiden, ist eine untere Schranke für die Komplexität von Sortier­verfahren. Diese untere Schranke wird informations­theoretische untere Schranke genannt. Nach der Informations­theorie beträgt die Anzahl der Ja/Nein-Entscheidungen für die Unterscheidung von n! verschiedenen Fällen log₂(n!).

Es ist leicht zu sehen, dass gilt:

n! (n/2)^n/2.

Somit gilt:

Jedes Sortier­verfahren, 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 Sortier­verfahren benötigt also mindestens proportional zu n log(n) viele Vergleiche, hat somit also eine Komplexität von Ω(n log(n)).

Die Sortier­verfahren 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 Sortier­verfahren, 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 informations­theoretische untere Schranke daher nicht zugleich eine untere Schranke für die Anzahl der Schritte.

 

 

Weiter mit:   [Bucket Sort und Radix Sort]   oder

 

H.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 13.04.2002   Updated: 14.10.2009