Sortieralgorithmen

Aus Infostudium Wiki

Inhaltsverzeichnis 1 Intuitive Algorithmen 1.1 Selection-Sort 1.2 Insertion-Sort 1.3 Bubble-Sort 2 Divide & Conquer Algorithmen 2.1 MergeSort 2.2 Heap-Sort 2.3 Quick-Sort 3 Spezielle Algorithmen 3.1 Bucket-Sort 3.2 Counting-Sort 3.3 Radix-Sort 4 Weblinks

Intuitive Algorithmen

Intuitive Sortieralgorithmen verfolgen eine Strategie, die vermutlich eine Mensch anwenden würde, falls er eine unüberschaubar große Menge von Daten sortieren sollte.

Selection-Sort

• Prinzip: Sei S der sortierte Teil des Arrays und U der unsortierte Teil. Am Anfang ist S noch leer, U entspricht dem ganzen Array. Das Sortieren durch Auswählen funktioniert so: Suche das kleinste Element in U und vertausche es mit dem ersten Element von U. Danach ist S um ein Element gewachsen, U um ein Element kürzer geworden. Anschließend wird das Verfahren solange wiederholt, bis der gesamte Array abgearbeitet worden ist.
• Das Verfahren arbeitet in-place mit einer Laufzeit von θ(n²).

Insertion-Sort

• Prinzip: Das Array wird in zwei Teile geteilt: Links der Ausgabebereich rechts der Eingabebereich Nach und nach werden die Elemente der Eingabeliste sortiert in die Ausgabeliste geschrieben.
• Das Verfahren arbeitet in-place mit einer Laufzeit von θ(n²).
• Unterschied zu SelectionSort: Bei SelectionSort wird das nächst größere Element aus der Eingabeliste herausgesucht (selektiert), wo hingegen bei InsertionSort die Elemente egal wie sie in der Eingabeliste sortiert sind nach und nach in die Ausgabeliste sortiert eingefügt.

Bubble-Sort

• Prinzip: Ein recht einfacher, aber daher auch einer mit einer hohen Laufzeitkomplexität. Bei jedem Durchlaufen der Liste werden immer zwei Elemente verglichen und bei Bedarf vertauscht. Nach n² Schritten ist er auf jeden Fall fertig.
• Das Verfahren arbeitet in-place mit einer Laufzeit von O(n²).

Divide & Conquer Algorithmen

Die divide & conquer-Verfahren zerlegen die Probleminstanzen rekursiv in kleinere Teile bis diese effizient gelöst werden können. Die Teillösungen werden auf eine spezielle Art zu einer Gesamtlösung zusammengesetzt.

MergeSort

• Prinzip: Durch ein verzahntes Einfügen ist es möglich, zwei bereits sortierte Folgen zu einer sortierten Folge zu verschmelzen. Das Verfahren zerlegt ein Array rekursiv in zwei etwa gleichgrosse Teilarrays (die Größe darf sich maximal in einer additiven Konstante unterscheiden). Die Zerlegung terminiert, falls das betrachtete Teilarray eine Größe von maximal eins hat. Diese Teilarrays sind trivialerweise sortiert. Beim Rücklauf der Rekursion werden die (nach Vorraussetzung sortieren) Arrays, wie anfangs beschrieben, zu einem neuen sortierten Array verschmolzen.
• Das Verfahren arbeitet nicht in-place mit einer Laufzeit von θ(nlog(n)).

Heap-Sort

• Prinzip: Ein Heap ist eine Datenstruktur die effizient als ein gekapseltes Array implementiert werden kann. Ein Heap ist ein höhenoptimaler Baum mit konstant beschränktem Verzweigungsgrad. Ein Min-Heap erfüllt die Bedingung, dass die Werte der Kindknoten nie echt kleiner als der Wert des Elternknotens ist (Max-Heap analog). Der Heap-Sort Algorithmus interpretiert das Eingabearray als Heap. Allgemein verletzen dabei aber einige Elemente die Heapbedingung. Hierzu werden die Elemente im Heap durch sukzessives Vertauschen auf- oder abwärts bewegt. Dadurch lässt sich in logarithmischer Zeit die Heapbedingung wiederherstellen. Da (bei einer intuitiven Implementierung) das erste Arrayelement die Wurzel des Heaps darstellt, ist bei einem Min-Heap, das erste Arrayelement das Minimum des Arrays. In jedem Schritt des Algorithmus lässt man jeweils das erste betrachtete Arrayelement fallen und befasst sich nurnoch mit dem Rest. Es kann wieder in logarithmischer Zeit die Heapbedingung für das restliche Array hergestellt werden. Generell lässt sich also Heap-Sort mit Selection-Sort vergleichen. Heap-Sort implementiert allerdings eine effizientere Art, dass jeweilige Extermum der Elemente zu finden.
• Das Verfahren arbeitet in-place mit einer Laufzeit von O(nlog(n)).

Quick-Sort

• Prinzip: Für zwei sortierte Array L,R und ein Element x mit . In diesem Fall ist die Folge, welche man gewinnt indem man die Element von L,x und R aneinanderreiht, natürlich sortiert. Verglichen zum Merge-Sort ist der Verschmelzungsschritt hier also sehr schnell. Die Zerlegung gestaltet sich jedoch ein wenig komplexer. Hierzu wird ein beliebiges Element x des Eingabearrays ausgewählt. Man beginnt mit . Nun geht man den Rest vom Array (ohne x selbst) schrittweise durch. Element die kleinergleich x sind werden in L eingefügt, die anderen landen in R. Nach diesem Schritt sind erfüllen die Mengen die obige Forderung nach . Da L und R aber noch nicht sortiert sind, führt man nun Quick-Sort rekursiv auf dieen Mengen aus.
• Das Verfahren arbeitet (unter geeigneter Implementierung) in-place mit einer worst-case-Laufzeit von O(n²), besitzt im probabilistischen Mittel jedoch eine erwartete Laufzeit von O(nlogn).

Spezielle Algorithmen

Die speziellen Verfahren stellen Ansprüche an die Datensätze und sind nicht auf beliebigen Daten anwendbar. Beispielsweise kann die Größe des Universums, die Kodierungslänge oder das Kodierungsalphabet eingeschränkt werden.

Bucket-Sort

• Prinzip: Beim Bucket-Sort sollen Elemente nach Klassen sortiert werden. Es wird ermittelt, wie viele Elemente in einer Klasse sind. Addiert man schrittweise die Anzahl der Elemente der Klassen, so ergeben sich Einfügestellen für die Ausgabeliste. Wenn man ein Element an der Einfügestelle einsortiert hat, so erhöht man die Einfügestelle.
• Das Verfahren arbeitet nicht in-place und sortiert n Elemente aus k Klassen in θ(n + m).

Counting-Sort

• Prinzip: Generell wie Bucket-Sort. Allerdings bleiben hierbei die Elemente nicht erhalten, sondern werden nach dem Auszählen in das Array überschrieben. Dieses Verfahren kann angewendet werden, wenn die charakteristische Größe der Schlüssel die einzige Charakteristik der Eingabedaten ist. Dies trifft beispielsweise auf Zahlen zu. Anders können Knoten eines Graphen nicht mit Counting-Sort nach ihrem Grad sortiert werden, da die Knoten neben ihrem Grad noch weitere Daten wie die Graphkonnektivität enthalten.
• Das Verfahren arbeitet in-place und sortiert n Elemente aus k Klassen in θ(n + m).

Radix-Sort

• Prinzip: Elemente werden anhand ihrer binären Kodierung im Computer sortiert. Hierzu verwendet der Algorithmus zwei Phasen. In der Partitionierungsphase werden die Elemente anhand ihres höchstwertigen Bits in zwei Klassen (0 oder 1) aufgeteilt. Anhand der folgenden Sammelphase werden die Elemente aus der Klassen ausgelesen und in der Reihenfolge im Array abgelegt. Danach sind die Elemente des Array bereits bezüglich ihres höchstwertigen Bits sortiert. Die Phasen werden nun für die jeweils zweit-höchstwertigen Bits ausgeführt, etc.
• Das Verfahren arbeitet nicht in-place und sortiert n Elemente aus k Klassen in θ(n + m). Da die Kodierungs der Element bei primitiven Datentypen konstant groß ist (beispielsweise durch 32-bit Darstellung geschieht), ist im Regelfall m eine Konstante. Damit ergibt sich eine Laufzeit von θ(n).

Weblinks

http://de.wikipedia.org/wiki/Sortierverfahren