Lexikon der Mathematik: Sortierverfahren
Verfahren, um eine Liste von Objekten R1,…,Rn, die sich jeweils aus einem Schlüssel Si und einer Information Ii zusammensetzen, in eine sortierte ListeRj1,…,Rjn der Objekte R1,…,Rn zu überführen.
Man unterscheidet zwischen allgemeinen Sortierverfahren und speziellen Sortierverfahren. Allgemeine Sortierverfahren nutzen während der Berechnung der Sortierung nur die auf der Menge der Schlüssel definierte totale Ordnung ≤ aus. Typische Vertreter für diese Klasse von Sortierverfahren sind die Verfahren Heapsort, Mergesort (Sortieren durch Mischen), Quicksort und Sortieren durch Maximumssuche bzw. durch Minimumssuche.
Sortierverfahren, die nicht nur die auf der Menge der Schlüssel definierte totale Ordnung ≤ ausnutzen, sondern auch die bei der gegebenen Probleminstanz vorhandene spezielle Struktur der Schlüssel, werden spezielle Sortierverfahren genannt. Typische Vertreter sind die Verfahren countingsort zum Sortieren ganzer Zahlen aus einem festen Bereich [1..k], Bucketsort zum Sortieren reeller Zahlen, und das Sortieren durch Fächerverteilung zum Sortieren von endlichen Wörtern über einem endlichen Alphabet.
Allgemeine Sortierverfahren benötigen zum Sortieren von n Objekten im schlechtesten Fall wenigstens [log2n!] Vergleiche, also ordnungsmäßig wenigstens n· [log2n] Schritte. Spezielle Sortierverfahren können hingegen eine Laufzeit haben, die linear in der Anzahl der zu sortierenden Wörter ist.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.