Wir stellen zwei Sortierverfahren vor, die im Gegensatz zu "herkömmlichen Verfahren" in linearer Zeit sortieren können, indem sie Annahmen über die Eingabemenge treffen. Diese sind Countingsort und Radixsort. Countingsort nimmt an, dass es sich ausschließlich um ganze Zahlen handelt, Radixsort nimmt an, dass die größte Ziffer kleiner als die Anzahl der zu sortierenden Zahlen ist.
Inhaltsverzeichnis
- Einleitung
- Grundlagen
- Definitionen
- O-Notation
- Sortieralgorithmen
- Stabile Sortieralgorithmen
- Speicherplatzverbrauch: In-Place und Out-of-Place
- Effizientes Sortieren
- Mergesort
- Lineares Sortieren
Zielsetzung und Themenschwerpunkte
Der Text beschäftigt sich mit Sortierverfahren, insbesondere mit Algorithmen, die in linearer Zeit sortieren können. Dabei werden die Verfahren Countingsort und Radixsort vorgestellt, die jeweils bestimmte Annahmen über die Eingabemenge treffen. Der Text beleuchtet die Effizienz und die Grenzen dieser Verfahren, indem er sie mit klassischen Sortierverfahren wie Mergesort und Bubblesort vergleicht.
- Lineare Sortieralgorithmen (Countingsort und Radixsort)
- Annahmen über die Eingabemenge
- Effizienz von Sortieralgorithmen
- Vergleich mit traditionellen Sortierverfahren
- Untere Schranke für vergleichsbasierte Algorithmen
Zusammenfassung der Kapitel
Einleitung
Die Einleitung erläutert die Bedeutung effizienter Sortierverfahren, insbesondere im Kontext von großen Datenmengen wie in Datenbanken oder Telefonbüchern. Die Bedeutung von Radixsort für die frühe Lochkartensystem wird hervorgehoben, wobei die Anwendung in modernen Computersystemen erwähnt wird.
Grundlagen
Dieses Kapitel definiert wichtige Begriffe wie Teilliste und O-Notation, die für das Verständnis der späteren Sortierverfahren essentiell sind. Die O-Notation ermöglicht die Klassifizierung von Algorithmen hinsichtlich ihrer Laufzeit und ihres Speicherplatzbedarfs.
Sortieralgorithmen
Der Abschnitt diskutiert stabile Sortieralgorithmen und ihre Eigenschaften. Der Unterschied zwischen In-Place- und Out-of-Place-Algorithmen wird erklärt. Das Kapitel führt das Mergesort-Verfahren ein, das einen Divide-and-Conquer-Ansatz verwendet, und stellt dessen Laufzeit und Speicherplatzverbrauch dar.
Lineares Sortieren
Dieses Kapitel befasst sich mit linearen Sortierverfahren. Es wird erklärt, dass die untere Schranke von (n · log(n)) für vergleichsbasierte Algorithmen nicht für lineare Sortieralgorithmen gilt, da diese bestimmte Annahmen über die Eingabemenge treffen. Die Einschränkungen der Eingabemenge für Verfahren wie Countingsort werden hervorgehoben.
Schlüsselwörter
Die Schlüsselwörter des Textes sind: Sortieren, Algorithmen, lineare Zeit, Countingsort, Radixsort, Mergesort, Eingabemenge, Annahmen, Effizienz, Laufzeit, Speicherplatz, O-Notation, Stabilität, In-Place, Out-of-Place, Entscheidungsbaum, untere Schranke, vergleichsbasiert.
- Citation du texte
- Sven Köhle (Auteur), 2017, Countingsort und Radixsort. Sortieren in linearer Zeit, Munich, GRIN Verlag, https://www.grin.com/document/377686
