Interne Sortieralgorithmen

Beschreibung / Inhalt
Das vorliegende Dokument beschäftigt sich mit dem Thema „Sortieren“. Der Autor erklärt zunächst, was unter dem Begriff zu verstehen ist und betont die Bedeutung des Sortierens in der Datenverarbeitung, da etwa 25% aller Rechenzeit im kommerziellen Bereich darauf entfallen. Es werden verschiedene Sortierverfahren wie „Selection Sort“, „Insertion Sort“, „Bubble Sort“, „Shell Sort“, „Quick Sort“ und „Heap Sort“ vorgestellt und jeweils mit einem Algorithmus und einem Beispiel erläutert.

Vor der Auswahl eines Sortieralgorithmus sollen laut Autor Kriterien wie Laufzeit, Speicherplatz und Stabilität betrachtet werden. Um die Unterschiede zwischen den Verfahren zu verdeutlichen, präsentiert das Dokument eine Tabelle mit Zeiten für ein bestimmtes n, für die jeweils sortierte, zufällige oder invers sortierte Folgen übergeben wurden. Die Messungen wurden unter bestimmten Bedingungen durchgeführt, etwa auf einem Amiga 500 mit einem „compilierten ACE-Programm“.

Das Dokument geht auf jedes der vorgestellten Sortierverfahren detailliert ein und gibt dabei auch Hinweise zu Best-Case-, Worst-Case- und Average-Case-Szenarien sowie zu möglichen Verbesserungen. Der Leser wird durch die informierende Darstellung befähigt, die verschiedenen Verfahren zu verstehen und nachvollziehen zu können, weshalb sich manche Verfahren in bestimmten Fällen als effektiver erweisen als andere.
Direkt das Referat aufrufen

Auszug aus Referat
Allgemein Was ist Sortieren überhaupt?Niklaus Wirth definiert Sortieren wie folgt: Unter Sortieren versteht man allgemein den Prozess des Anordnens einer gegebenen Menge von Objekten in einer bestimmten Ordnung. 1 , Kapitel 2, Seite 77Das Sortieren hat in der Datenverarbeitung einen sehr hohen Stellenwert. Circa 25 aller Rechenzeit im kommerziellen Bereich entfällt auf das Sortieren von Daten 2 . An Beispielen zum Sortieren mangelt es nicht: Telefonbücher, Wörterbücher, Verzeichnisse, ... Um Interne Sortieralgorithmen anwenden zu können, muß es möglich sein, auf die einzelnen Datensätze direkt zuzugreifen (entweder im Hauptspeicher oder mittels einer geeigneten Datei).Heutzutage sind schon sehr viele solcher Algorithmen bekannt. Einige sollen hier vorgestellt werden. Sortierverfahren Vor der Auswahl eines Sortieralgorithmus sollte man einige Kriterien betrachten: LaufzeitDie Laufzeit für das Sortieren von n Datensätzen ist abhängig von der Anzahl der Vergleichsoperationen, der Anzahl der Datensatzbewegungen, der Datensatzgröße, usw. SpeicherplatzWird eine Kopie der Sortierfolge im Hauptspeicher gehalten? StabilitätEin Sortierverfahren gilt als stabil, wenn bei Elementen mit gleichem Sortier-Schlüssel die ursprüngliche Reihenfolge erhalten bleibt. Selection Sort (Ripple Sort) Algorithmus finde das kleinste Element in der Folge Restfolge und tausche es mit dem ersten Element der Folge Restfolge kleinstes Element der Folge Restfolge an der richtigen Stelle; Restfolge um dieses ...
Direkt das Referat aufrufen