Relevante Nichtsortieralgorithmen

Sortieralgorithmen verwenden teilweise weitere für sie relevante Algorithmen, die für ihre Eigenschaften, vor allem die Sortiergeschwindigkeit, die (In-)Stabilität und den Speicherbedarf signifikant sind:

  • (Natural-)Mergesort: Hier ist das Verschmelzen (Merge / Merging) jeweils zweier oder mehrerer schon sortierter Blöcke bzw. Teilarrays, das in diesem Kontext nur allzugern und -oft fälschlicherweise mit „(Ver-)Mischen“ übersetzt wird, vonnöten. Man kann dazu einen Sortieralgorithmus verwenden oder auch auf einen solchen verzichten, denn die Sortiertheit dieser Blöcke ist ja schon gegeben und kann zur Effizienzsteigerung ausgenutzt werden. Das Verschmelzungsproblem ist demnach kein Sortierproblem (auch wenn es als solches so gelöst werden kann / könnte, da das Ergebnis des Verschmelzens eine sortierte (Teil-)Menge ist, was allerdings ineffizient ist). Es ist sozusagen ein Spezialfall des Sortierens mit besonderen Voraussetzungen / Bedingungen. Die einfachste und schnellste Variante („ex situ“) besteht im Kopieren in zusätzlichen Speicher und Zurückkopieren, wobei es egal ist, ob beim ersten oder zweiten Kopieren das Verschmelzen geschieht. Im Minimalfalle dieses Ex-Situ-Verschmelzens kommt man mit einem Zusatzspeicher aus, der nur so groß wie der kleinere Block ist, also maximal die Hälfte der Summe beider Blöcke. Schwieriger, komplizierter und langsamer wird es mit vermindertem Zusatzsspeicher oder gar ohne zusätzlichen Speicher („in situ“). Es gibt dermaßen viele Verschmelzungsalgorithmen, daß diese das Mergesort fast schon als eine eigene Sortieralgorithmenklasse begründen. Teilweise müssen die Blöcke die gleiche Elementeanzahl beinhalten, oder der zweite, „hintere“, „rechte“ Block muß der größere sein, d.h., die größere Elementeanzahl beinhalten, damit das Verschmelzen funktioniert, sodaß es Einschränkungen gibt (kein Naturalmergesort, Elementeanzahl muß 2er-Potenz sein). Wird statt des Verschmelzens beider Blöcke ein Sortieralgorithmus, nämlich das Mergesort selbst (rekursiv) aufgerufen, entsteht Slowsort, ein äußerst langsamer Sortieralgorithmus (ein Vergleichs- und optionaler Tauschbefehl kommen noch hinzu, damit überhaupt sortiert werden kann). Es gibt stabile und nichtstabile Mergingalgorithmen, allerdings wird ein Mergesort mit nichtstabilem Merging seines wichtigsten Vorteiles gegenüber anderen schnellen Sortieralgorithmen beraubt (Quick- und Heapsort sind nicht stabil). Weiterhin ist auch das Verschmelzen von mehr als zwei Blöcken (k-way Merge, k>2) „in einem Zuge“ möglich. Das Verschmelzen kann sogar parallelisiert werden. Dieses Verschmelzen läuft zudem umso effizienter ab, je mehr sich die Größen (Elementeanzahlen) der beiden verschmelzenden Teilmengen angleichen. Je kleiner hingegen eine gegenüber der anderen ist, desto eher wird es ein ineffizientes Einfügen. Deshalb geschieht z.B. beim Naturalmergesort das Verschmelzen „stufenweise“. Verschmölze man hingegen jede neu gefundene, „natürlich“ sortierte Teilmenge mit der schon vom Algorithmus sortierten Teilmenge, wird es dem Insert(ion)sort ähnlich und ziemlich langsam.
  • Einige Sortieralgorithmen (Symmetry Partition Sort sowie einige (Natural-)Mergesort, konkret deren Merging- / Verschmelzungsalgorithmen) beinhalten das Vertauschen Vertauschen („Block swapping“, „Arrayrotation“) ebenfalls bereits sortierter, i.d.R. verschiedengroßer Blöcke (das Vertauschen gleichgroßer Blöcke ist hingegen trivial: Tausch der beiden ersten Elemente, zweiten usw.). Sofern die Blöcke verschieden groß sind, müssen sie benachbart sein. Für das Blöcke(ver)tauschen können acht verschiedene Block(ver)tauschalgorithmen mit unterschiedlichen Merkmalen gewählt werden. Sofern es Elemente mit gleichgroßem Sortierelement bzw. -schlüssel in beiden Blöcken gibt, geht die Stabilität verloren, allerdings ist erstaunlicherweise das HP-/SGI-Mergesort trotz diesem Blöcke(ver)tauschen stabil: Dort wird vermieden, Blöcke zu tauschen, die gleichgroße Elemente(schlüssel) in beiden Blöcken beinhalten. Das Block(ver)tauschproblem ist ebenfalls kein Sortierproblem. Im Gegensatz zum Verschmelzen ist auch nicht gewiß, daß miteinander sortierte statt vertauschter Blöcke zu einem fehlerfreien Ergebnis führen.
  • Zwei Verschmelzungsalgorithmen (sog. Shufflemerges, der eine Algorithmus von John Ellis und Minko Markow, das andere Shufflemerge von Elif Acar & Co.) beinhalten das sog. „Shuffling“ (angelehnt an eine Spielkartenmischmethode), das sich am ehesten mit „(Ineinander)Verzahnen“ (wie bei einem Reißverschluß) übersetzen läßt. Das ist gewissermaßen ein besonderes Verschmelzen (s. 1. Punkt) unter Vernachlässigung der Größe der Elemente(schlüssel). Aus den (fast gleichgroßen, maximal 1 Stelle Unterschied) Folgen 1, 2, 3... und A, B, C... ist die Folge 1, A, 2, B, 3, C... (inner shuffling) bzw. A, 1, B, 2, C, 3... (outer shuffling) zu generieren. Weicht die Elementeanzahl um 1 ab, gibt es nur eine Möglichkeit des vollständigen Verzahnens. Beim Shuffling gilt das gleiche wie beim Verschmelzen und beim Blöcketausch: Ist genug extra Speicherplatz für dieses Vereinen vorhanden, ist es simpel, bei minimalem zusätzlichen Speicherplatz hingegen anspruchsvoll und schwierig, insbesondere, wenn die Geschwindigkeit hochbleiben soll. Grundsätzlich ist man bei der Wahl des Shufflingalgorithmus' genauso frei wie bei der Wahl des Merging- und Blocktauschalgorithmus, jedoch wurden die gewählten Shufflingalgorithmen der originalen Quelltext belassen (die beiden Mergingalgorithmen benutzen je einen anderen). Der inverse Vorgang, das „Entzahnen“ oder auch Unshuffling, ist bei beiden Mergingalgorithmen ebenfalls vonnöten.
  • Eine zentrale Vorgehensweise einiger Sortieralgorithmen (Circle,- Quick- und Splitsort) ist die Aufspaltung einer jeden (Teil-)Menge in zwei Teile, nämlich einen Teil mit den kleineren und einen mit den größeren Elementen, die sog. Partitionierung. Diese Teile sind nicht zwangsläufig gleich groß, also Hälften (das sind sie nur beim Circlesort). Da diese Aufspaltung aber zu einer ersten groben Ordnung, zu einer Art Vorsortierung führt, ist sie eigentlich schon ein „halber“ Sortieralgorithmus. Am effektivsten (schnell und speichersparend) geschieht diese Partitionierung beim Quicksort und auch beim Circlesort, nur ist sie dort leider instabil. Bestrebungen, dieses zu stabilisieren, führten zu den verschiedenen Splitsorts, was jedoch spürbar langsamer (insbesondere bei verschieden strukturierten Startmengen) und speicherintensiver wird. Überzeugend hinsichtlich der Geschwindigkeit wird die Partitionierung in den beiden stabilen Quicksorts, allerdings sind diese Algorithmen sehr kompliziert.

Kontaktformular