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. Mischen assoziiert jedoch das Kartenmischen, demnach die Erhöhung der Unordnung, beim Verschmelzen wird hingegen geordnet. 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), jedenfalls kein allgemeines für beliebige Unordnungen. Es ist sozusagen ein Spezialfall des Sortierens mit besonderen Voraussetzungen / Bedingungen. Das Verschmelzen ist das zentrale Unterprogramm jeglicher Mergealgorithmen und das einzige, das das Ordnungsniveau erhöht; es wird lediglich geschickt wiederholt angewandt, bis die gesamte Menge sortiert ist. Die einfachste und schnellste Variante („ex situ“) besteht im Kopieren in zusätzlichen Speicher und Zurückkopieren, wobei es im Zeitalter zugriffsflexibler Speicher nunmehr egal ist, ob beim ersten oder zweiten Kopieren das Verschmelzen geschieht (in früheren Zeiten, als noch externe Bandspeicher genutzt wurden, war das Verschmelzen erst beim Zurückkopieren effizient). Im Minimalfalle dieses Ex-Situ-Verschmelzens kommt man mit einem Zusatzspeicher aus, der nur so groß wie der kleinere Block ist (Scratchmerge). Schwieriger, komplizierter und langsamer wird es mit vermindertem Zusatzsspeicher (Speicherzellenanzahl meistens die Wurzel der Anzahl zu verschmelzender Elemente) oder gar ohne zusätzlichen Speicher („in situ“) bis auf die eine unvermeidliche Speicherzelle für das Vertauschen. Eine besonders naheliegende Variante für in situ sind m.E. die vereinfachten Verschmelzungen nach Mannila und Ukkonen. 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 in mehreren Durchgängen. 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. Zuguterletzt müssen die zu verschmelzenden Teilfolgen gar nicht voneinander getrennt (möglichst aber nebeneinander) im Speicher angeordnet sein; sie können vielmehr auch „verzahnt“ sein, wovon das Bitwise Sorting Network von Ian Parberry (im Programm implementiert) profitiert.
  • Einige Sortieralgorithmen (Symmetry Partition Sort und einige (Natural-)Mergesorts, konkret deren Merging- / Verschmelzungsalgorithmen) beinhalten das 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 jeweils beiden ersten Elemente, zweiten usw.). Sofern die Blöcke verschieden groß sind, müssen sie benachbart sein. Das gleiche Ergebnis erhält man auch, wenn man das (Teil-)Array „rotieren“, d.h. zyklisch verschieben läßt, nämlich um die Anzahl an Stellen, wie die Elementeanzahl des kleineren Blockes beträgt. 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 (AKS-, Circle,- Quick- und Splitsort) ist die Aufspaltung einer jeden (Teil-)Menge in (meistens) zwei Teile (Partitionen), 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ß im Sinne gleicher Elementeanzahlen („balanciert“), also Hälften (das sind sie nur beim AKS- und beim Circlesort). Außerdem kann diese Partitionierung perfekt (das Maximum der Partition mit den kleineren Elementen ist nicht größer als das Minimum der Partition mit den größeren Elementen, z.B. beim Quicksort), oder unvollständig sein (dort gilt diese Bedingung nicht, Circlesort). Besteht die zu sortierende Menge nur aus Elementen mit „binärer“ Merkmalsausprägung (z.B. Männlein und Weiblein oder Schrauben und Muttern), am Computer am ehesten Nullen und Einsen, beim Zwei-Pivot-Quicksort sogar bei drei unterschiedlichen Elementetypen/-größen, so stellt die Partitionierung bereits einen vollwertigen Sortieralgorithmus, ansonsten eben nur eine erst Grobsortierung dar. Es gibt zudem eine Partitionierung mit ternärer Aufspaltung der Menge (kleiner, gleich oder größer als das sog. Referenz- oder Pivotelement). Die Partitionierung ist das zentrale Vorgehen von Quicksort & Co. und das einzige Unterprogramm, das das Ordnungsniveau erhöht. Die Sortierung der Gesamtmenge erfolgt in Form seines geschickten, wiederholten Aufrufens. 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 verschiedenen stabilen Quicksorts, allerdings sind diese Algorithmen sehr kompliziert. Die Aufspaltung in drei Partitionen erfolgt beim Trisort (ein Ex-Situ-Quicksort) sowie beim 3-Wege- und Dual-Pivot-Quicksort. Bei der von mir entwickelten Verallgemeinerung der Lomuto-Partitionierung ist die Aufspaltung des (Teil-)Arrays sogar bei fast beliebig vielen (n) Pivotelementen und mithin in fast beliebig viele (n+1) Partitionen möglich, konvergiert dann aber zu einem echten, klassischen Sortieralgorithmus (Insertionsort und wird entsprechend langsam).

Die Partitionierung (Menge in Teilmengen aufspalten) und das Verschmelzen (Menge durch Vereinigen von Teilmengen bilden) sind in gewisser Weise gegensätzliche Algorithmen, obwohl beide das Ordnungsniveau heben. Das Simpleswapmerge nach Siegfried Sielaff bedient sich beider Konzepte.

Kontaktformular