Flashsort ist ein Sortierverfahren, das auf Verteilung (englisch distribution sorting) basiert. Es weist eine lineare Komplexität für gleichverteilte Eingabedaten auf.

Die Idee hinter Flashsort ist, dass eine Datenmenge mit bekannter Wahrscheinlichkeitsverteilung vorgegeben ist, die es erleichtert, unmittelbar abzuschätzen, wohin ein Element im Rahmen der Sortierung etwa positioniert werden soll, wenn die untere und obere Schranke des Wertebereichs bekannt sind. Wenn beispielsweise eine gleichförmig verteilte Zahlenmenge gegeben ist, deren Minimum 1 und deren Maximum 100 ist, dann ist es eine gute Annahme, dass ein Element mit dem Wert 50 ungefähr in der Mitte der sortierten Menge zu liegen kommen wird. Diese ungefähre Position nennt man in diesem Sortierverfahren Klasse. Wenn die Elemente von   bis   nummeriert sind, dann berechnet sich die Klasse des Elements   wie folgt:

 ,

wobei   die unsortierte Eingabemenge ist. Der Bereich, der durch jede Klasse abgedeckt wird, ist (etwa) gleich groß, bis auf die letzte Klasse, die nur das Maximum oder die Maxima enthält. Diese Klassifikation stellt sicher, dass jedes Element in einer bestimmten Klasse größer ist als jedes Element in einer niedrigeren Klasse. Dies sorgt für eine partielle Ordnung der Daten und reduziert die Anzahl der Inversionen. Insertionsort (Sortierung durch Einfügen) wird auf die klassifizierte Menge angewendet. Solange die Eingabedaten gleichförmig (englisch uniformly) verteilt sind, sind diese Klassen etwa gleich groß, enthalten also nur wenige Elemente, so dass die Sortierung innerhalb der Klassen effizient durchgeführt werden kann.[1]

Hauptspeichereffiziente Implementierungen

Bearbeiten

Um Flashsort mit geringen Hauptspeicheranforderungen auszuführen, kann man darauf verzichten, für die Klassen eigene Datenstrukturen zu verwenden. Stattdessen werden die oberen Grenze jeder Klasse der Eingabedatenliste   in einem Hilfsvektor   abgelegt. Diese oberen Grenzen können ermittelt werden, indem man bei einem Durchlauf durch alle Daten die Anzahl der Elemente in jeder Klasse berechnet. Die obere Grenze einer Klasse ist dann die obere Grenze der vorigen Klasse plus die Anzahl der Elemente in der Klasse selbst. Die Elemente dieses Vektors können als Zeiger zu den Klassen verwendet werden.

Die Verteilung auf die Klassen wird durch eine Serie von Zyklen implementiert, wobei Element auf dem Eingabevektor   entnommen wird und seine Klasse berechnet wird. Die Zeiger im Vektor   werden verwendet, um dieses Element in eine freie Position innerhalb der passenden Klasse einzufügen. Nach dem Einfügen wird dieser Zeiger dekrementiert. Das Einfügen findet in den Vektor   selbst statt und verdrängt ein anderes Element, das dann als Nächstes in die passende Position eingefügt wird. Dieser Zyklus endet, wenn ein Element in die Position eingefügt wird, aus der das erste Element des Zyklus kam.

Ein Element ist ein gültiges Startelement für einen Zyklus, wenn es noch nicht klassifiziert worden ist. Während der Algorithmus über den Eingabevektor   iteriert, werden die bereits klassifizierten Elemente ausgelassen und unklassifizierte Elemente werden jeweils verwendet, um einen neuen Zyklus zu starten. Man kann ohne weitere Hilfsstrukturen für die einzelnen Elementen entscheiden, ob ein bestimmtes Element schon klassifiziert worden ist: Ein Element ist genau dann klassifiziert worden, wenn sein Index größer als der Zeiger im Hilfsvektor   ist. Um dies zu beweisen, betrachte man den augenblicklichen Index des Vektors  , den der Algorithmus gerade bearbeitet. Sei   dieser Index. Die Elemente   bis   sind bereits klassifiziert worden und in die richtige Klasse eingefügt worden. Angenommen   ist größer als der Zeiger zur Klasse des Elemente  . Es wird jetzt angenommen, dass   unklassifiziert ist und damit legitimerweise an dem Index, der durch seinen Klassenzeiger spezifiziert wird, eingefügt werden kann, wo es ein klassifiziertes Element in einer anderen Klasse ersetzen würde. Dies ist aber unmöglich, da die initialen Zeiger jeder Klasse auf deren oberen Grenzen zeigen, was sicherstellt, dass der exakt benötigte Platz für jede Klasse des Eingebevektors   bereitgestellt wird. Deshalb ist jedes Element aus der Klasse des Elements  , einschließlich des Elements   selbst, bereits klassifiziert worden. Wenn also ein Element schon klassifiziert worden ist, dann ist der Zeiger dieser Klasse um   verringert worden und damit unterhalb des neuen Indexes des Elements.[1][2]

Leistung / Komplexität

Bearbeiten

Überlegungen zur Leistung (englisch Performance) umfassen den Hauptspeicherbedarf und den Zeitaufwand für die Sortierung. Der einzige zusätzlich benötigte Speicher ist für den Hilfsvektor   erforderlich, um die Grenzen der Klassen zu speichern, sowie eine konstante Anzahl von skalaren Variablen, die während der Berechnung benötigt werden.

Im Idealfall einer ausgeglichenen Eingabedatenmenge hat jede Klasse etwa dieselbe Größe und das Sortieren der individuellen Klassen hat die Komplexität  . Falls die Anzahl   der Klassen proportional zu der Größe der Eingabedatenmenge   ist, ergibt sich die Laufzeit aus der Sortierung innerhalb der Klassen, die   ist. Im schlimmsten Fall, wenn alle Elemente in einer oder ganz wenigen Klassen landen, wird die Komplexität des Algorithmus als Ganzes durch die Performance des Insertionsort innerhalb der Klassen dominiert. In diesem Fall erhält man  . Varianten des Algorithmus verbessern die Performance in diesem Fall, indem sie bessere Algorithmen für die Sortierung innerhalb der Klassen verwenden, z. B. Quicksort oder rekursives Flashsort auf den Klassen, die eine gewisse Größe überschreiten.[2][3]

Für die richtige Wahl von  , der Anzahl der Klassen, muss die Zeit für die Klassifizierung der Elemente (kleines   günstig) und die Zeit, die für die Sortierung innerhalb der Klassen benötigt wird (großes   günstig), gegeneinander aufgewogen werden. Basierend auf seinen Forschungsergebnissen fand Neubert, dass   optimal ist.

Bezüglich des Hauptspeichers vermeidet Flashsort den Aufwand, der für das Speichern der Klassen in dem sehr ähnlichen Bucketsort benötigt wird. Für   mit gleichförmig verteilten Daten ist Flashsort für alle   schneller als Heapsort und für   schneller als Quicksort. Etwa bei   wird es doppelt so schnell wie Quicksort.[1]

Wegen des Klassifizierungsprozesses ist Flashsort nicht stabil.

Abgrenzung

Bearbeiten

Der von Neubert als Flashsort vorgestellte Algorithmus hat den gleichen Namen wie ein älterer randomisierter Sortieralgorithmus für parallele Rechnerarchitekturen.[4][5][6]

Siehe auch

Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b c Karl-Dietrich Neubert: The Flashsort Algorithm. In: Dr. Dobb's Journal. Februar 1998, S. 123 (ddj.com [abgerufen am 6. November 2007]).
  2. a b Karl-Dietrich Neubert: The FlashSort Algorithm. 1998, abgerufen am 6. November 2007.
  3. Li Xiao, Xiaodong Zhang, Stefan A. Kubricht: Cache-Effective Quicksort. In: Improving Memory Performance of Sorting Algorithms. Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795, archiviert vom Original am 2. November 2007; abgerufen am 6. November 2007.
  4. http://nist.gov/dads/HTML/flashsort.html
  5. John H. Reif und Leslie G. Valiant: A logarithmic time sort for linear size networks. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing. 1983, S. 10–16, doi:10.1145/800061.808727.
  6. John H. Reif und Leslie G. Valiant: A logarithmic time sort for linear size networks. In: Journal of the ACM. Band 34, Nr. 1, 1987, S. 60–76, doi:10.1145/7531.7532.

Literatur

Bearbeiten
  • Karl-Dietrich Neubert: The Flashsort Algorithm. In: Dr. Dobb's Journal. Februar 1998, S. 123 (ddj.com).
  • Karl-Dietrich Neubert: The FlashSort Algorithm. In: Proceedings of the euroFORTH '97. September 1997 (bournemouth.ac.ukohne Peer-Review).
  • Apostolos Burnetas und Daniel Solow und Rishi Agarwal: An analysis and implementation of an efficient in-place bucket sort. In: Acta Informatica. Band 34, Nr. 9, 1997, S. 687–700, doi:10.1007/s002360050103 (1995 eingereicht).
  • E. J. Isaac und R. C. Singleton: Sorting by Address Calculation. In: Journal of the ACM. Band 3, Nr. 3, Juli 1956, S. 169–174, doi:10.1145/320831.320834.
Bearbeiten