Sortierverfahren

Untere Schranken für das Sortieren

 English version  aufwärts

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! größer gleich (n/2)n/2.

Somit gilt:

log(n!) größer gleich log((n/2)n/2)
  =  n/2 · log(n/2)
   Element  Ω(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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 13.04.2002   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik