Sortierverfahren

Vorherige Seite Inhaltsverzeichnis Nächste Seite

Sortieren: Definition und Bedeutung

Die Aufgabe des Sortierens ist, es Eingabedaten (Liste von sog. Schlüsseln) in eine bestimmte Ordnung zu bringen (aufsteigend oder absteigend). In diesem Lernprogramm werden die Schlüssel in aufsteigende Ordnung gebracht.

Sortieren ist in der Praxis sehr wichtig. In sortierten Listen lassen sich z. B. Elemente schnell finden und Duplikate aufspüren.

Anwendungsgebiet des Heapsort

Heapsort lässt sich unter den folgenden Bedingungen anwenden:

Laufzeitvergleich von Heapsort und Quicksort

Quicksort ist ein weiteres Sortierverfahren, das unter diesen Bedingungen arbeitet. Da Quicksort als der schnellste Sortieralgorithmus gilt, wird im Folgenden die Laufzeit von Quicksort und Heapsort verglichen.

Laufzeit Heapsort Laufzeit Quicksort
Mittlerer Fall Theta(n log n) Theta(n log n)
Aber um konstanten Faktor schneller!
Schlechtester Fall O(n log n) O(n^2)
Dieser Fall ist sehr unwahrscheinlich!

Der schlechteste Fall ist bei einer guten Quicksort-Variante sehr unwahrscheinlich. Da Quicksort im Mittel schneller ist, wird in der Praxis meist Quicksort verwendet. Für Anwendungen, bei denen man das Risiko nicht eingehen kann, dass es doch einmal zur Laufzeit O(n^2) kommt, empfiehlt es sich aber Heapsort einzusetzen.


Vorherige Seite Inhaltsverzeichnis Nächste Seite