Sortierverfahren

Untere Schranken für das Sortieren

 English version  aufwärts

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

Die Anzahl der Ja/Nein-Ent­scheidungen, die notwendig sind, um die unter­schiedlichen Permutationen voneinander zu unter­scheiden, ist eine untere Schranke für die Komplexität von Sortier­verfahren. Diese untere Schranke wird informations­theoretische untere Schranke genannt. Nach der Informationstheorie beträgt die Anzahl der Ja/Nein-Ent­scheidungen für die Unter­scheidung von n! ver­schiedenen 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 Sortier­verfahren, das auf Vergleichen beruht, bezieht seine Information aus­schließ­lich aus Ja/Nein-Ent­scheidungen, 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 dar­gestellten 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   up

 

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


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