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
1 Einleitung
2 Grundlagen
2.1 Definitionen
2.2 O-Notation
3 Sortierverfahren
3.1 Stabile Sortieralgorithmen
3.2 Speicherplatzverbrauch: In-Place und Out-of-Place
3.3 Effizientes sortieren
3.3.1 Mergesort
4 Lineares Sortieren
4.1 Countingsort
4.1.1 Voraussetzungen und Funktionsweise
4.1.2 Pseudocode
4.1.3 Beispiel
4.1.4 Laufzeit und Korrektheit
4.1.5 Stabilität
4.2 Radixsort
4.2.1 Funktionsweise
4.2.2 Pseudocode
4.2.3 Beispiel
4.2.4 Laufzeit und Terminierung
4.2.5 Korrektheit
5 Zusammenfassung / Ausblick
Zielsetzung & Themen der Arbeit
Die vorliegende Arbeit untersucht Sortierverfahren, die eine lineare Laufzeit erreichen, indem sie spezifische Annahmen über die zu sortierende Eingabemenge treffen, anstatt sich auf allgemeine, vergleichsbasierte Methoden zu stützen.
- Grundlagen der algorithmischen Komplexität und O-Notation
- Analyse stabiler Sortieralgorithmen und Speicherplatzanforderungen
- Detaillierte Untersuchung des Countingsort-Algorithmus
- Funktionsweise und Implementierung von Radixsort
- Bewertung der Leistungsfähigkeit und Voraussetzungen linearer Sortierverfahren
Auszug aus dem Buch
4.1.1 Voraussetzungen und Funktionsweise
Sei k ∈ Z . Jedes Eingabeelement m ist eine ganze Zahl m ∈ {0, ..., k}. Die Anzahl der Eingabeelemente bezeichnen wir mit n ∈ N. Hier kommt wieder eine wichtige Einschränkung: Countingsort kann nur sehr begrenzt angewandt werden, insbesondere können nur ganze Zahlen sortiert werden. Wenn etwas anderes sortiert werden soll, muss jedem Element ein sinnvoll gewählter Schlüssel zugewiesen werden (was meistens den Zeitvorteil zunichtemacht). Die Idee hinter dem Algorithmus ist wie folgt: Man bestimmt für jedes Eingabeelement m die Anzahl der Elemente, die kleiner als m sind. Diese Information wird verwendet, um m direkt an der richtigen Position einzuordnen. Wenn nun 10 Elemente kleiner sind als m, dann muss m an Position 11 eingeordnet werden. Dieser Algorithmus muss nun nur noch für gleiche Eingaben angepasst werden, da sonst gleiche Elemente immer überschrieben würden und so verloren gingen [CLRS01].
Wie wir unten sehen werden, hängt die Laufzeit von Countingsort auch von der größten Zahl k ab. Daher ist es unsinnig, mit Countingsort Mengen sortieren zu wollen, bei welchen n im Verhältnis zu k relativ klein ist. In der Praxis sind derart unsinnige Eingabemengen selten, meist ist k = O(n). Dies zeigt aber auch, dass man vor der Verwendung des Algorithmus prüfen sollte, ob es überhaupt sinnvoll ist, den Algorithmus hier einzusetzen.
Zusammenfassung der Kapitel
1 Einleitung: Einführung in die Notwendigkeit effizienter Sortierverfahren in der Informatik und Vorstellung der Algorithmen Countingsort und Radixsort.
2 Grundlagen: Definition mathematischer Notationen und der O-Notation zur Einordnung der Laufzeit von Algorithmen.
3 Sortierverfahren: Diskussion der Eigenschaften stabiler Sortierverfahren, Speicherplatznutzung sowie der unteren Schranke für vergleichsbasierte Algorithmen.
4 Lineares Sortieren: Detaillierte Analyse der nicht-vergleichsbasierten Algorithmen Countingsort und Radixsort inklusive deren Funktionsweise, Laufzeit und Korrektheitsbeweisen.
5 Zusammenfassung / Ausblick: Kritische Würdigung des Nutzens linearer Sortieralgorithmen unter Berücksichtigung ihrer spezifischen Anforderungen an die Eingabedaten.
Schlüsselwörter
Sortierverfahren, Lineare Laufzeit, Countingsort, Radixsort, O-Notation, Algorithmen, Informatik, Stabilität, In-Place Sortierung, Komplexität, Datenstrukturen, Eingabemenge, Effizienz, Speicherplatz, Sortieralgorithmen.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit speziellen Sortieralgorithmen, die eine lineare Laufzeit erreichen, sofern bestimmte Annahmen über die zu sortierenden Eingabedaten getroffen werden können.
Was sind die zentralen Themenfelder?
Die zentralen Felder sind die algorithmische Effizienz, die mathematische Analyse der Laufzeit (O-Notation) sowie die praktische Implementierung und Funktionsweise von Countingsort und Radixsort.
Was ist das primäre Ziel der Arbeit?
Das primäre Ziel ist es aufzuzeigen, wie durch das Treffen von Annahmen über die Eingabesequenz die unteren Laufzeitschranken vergleichsbasierter Sortierverfahren (Ω(n log n)) umgangen werden können.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt die algorithmische Analyse, formale Definitionen der Komplexität sowie Beweisführungen über die Korrektheit und Laufzeit von Algorithmen.
Was wird im Hauptteil behandelt?
Der Hauptteil behandelt theoretische Grundlagen, Anforderungen an Stabilität und Speicherplatz bei Sortieralgorithmen sowie eine detaillierte Aufarbeitung von Countingsort und Radixsort.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Schlüsselwörter sind Sortierverfahren, Lineare Laufzeit, Countingsort, Radixsort, O-Notation und Komplexitätsanalyse.
Warum ist die Stabilität bei Radixsort so entscheidend?
Stabilität ist notwendig, da Radixsort Zahlen basierend auf ihren Stellen sortiert; würde das zugrundeliegende Sortierverfahren (z.B. Countingsort) die Reihenfolge bei gleichen Werten verändern, gingen Informationen der vorherigen Durchläufe verloren.
Welche Einschränkung hat Countingsort gegenüber anderen Verfahren?
Countingsort ist primär auf ganze Zahlen in einem begrenzten Wertebereich beschränkt und benötigt, abhängig vom Parameter k, zusätzlichen Speicherplatz, was es für bestimmte Eingabemengen ineffizient machen kann.
- Quote paper
- Sven Köhle (Author), 2017, Countingsort und Radixsort. Sortieren in linearer Zeit, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/377686
