Flashsort

Flashsort ist ein Sortierverfahren, das auf Verteilung (englisch distribution sorting) basiert. Es weist eine lineare Komplexität ${\displaystyle {\mathcal {O}}(n)}$ für gleichverteilte Eingabedaten auf.

Konzept

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 ${\displaystyle 1}$ bis ${\displaystyle m}$ nummeriert sind, dann berechnet sich die Klasse des Elements ${\displaystyle A_{i}}$ wie folgt:

${\displaystyle K(A_{i})=1+\operatorname {int} \left((m-1){\frac {A_{i}-A_{\text{min}}}{A_{\text{max}}-A_{\text{min}}}}\right)}$,

wobei ${\displaystyle A}$ 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

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 ${\displaystyle A}$ in einem Hilfsvektor ${\displaystyle L}$ 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 ${\displaystyle A}$ entnommen wird und seine Klasse berechnet wird. Die Zeiger im Vektor ${\displaystyle L}$ 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 ${\displaystyle A}$ 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 ${\displaystyle A}$ 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 ${\displaystyle L}$ ist. Um dies zu beweisen, betrachte man den augenblicklichen Index des Vektors ${\displaystyle A}$, den der Algorithmus gerade bearbeitet. Sei ${\displaystyle i}$ dieser Index. Die Elemente ${\displaystyle A_{0}}$ bis ${\displaystyle A_{i-1}}$ sind bereits klassifiziert worden und in die richtige Klasse eingefügt worden. Angenommen ${\displaystyle i}$ ist größer als der Zeiger zur Klasse des Elemente ${\displaystyle A_{i}}$. Es wird jetzt angenommen, dass ${\displaystyle A_{i}}$ 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 ${\displaystyle A}$ bereitgestellt wird. Deshalb ist jedes Element aus der Klasse des Elements ${\displaystyle A_{i}}$, einschließlich des Elements ${\displaystyle A_{i}}$ selbst, bereits klassifiziert worden. Wenn also ein Element schon klassifiziert worden ist, dann ist der Zeiger dieser Klasse um ${\displaystyle 1}$ verringert worden und damit unterhalb des neuen Indexes des Elements.[1][2]

Leistung / Komplexität

Ü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 ${\displaystyle L}$ 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 ${\displaystyle {\mathcal {O}}(1)}$. Falls die Anzahl ${\displaystyle m}$ der Klassen proportional zu der Größe der Eingabedatenmenge ${\displaystyle n}$ ist, ergibt sich die Laufzeit aus der Sortierung innerhalb der Klassen, die ${\displaystyle m*{\mathcal {O}}(1)={\mathcal {O}}(m)={\mathcal {O}}(n)}$ 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 ${\displaystyle {\mathcal {O}}(n^{2})}$. 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 ${\displaystyle m}$, der Anzahl der Klassen, muss die Zeit für die Klassifizierung der Elemente (kleines ${\displaystyle m}$ günstig) und die Zeit, die für die Sortierung innerhalb der Klassen benötigt wird (großes ${\displaystyle m}$ günstig), gegeneinander aufgewogen werden. Basierend auf seinen Forschungsergebnissen fand Neubert, dass ${\displaystyle m=0{,}42\,n}$ 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 ${\displaystyle m=0{,}1\,n}$ mit gleichförmig verteilten Daten ist Flashsort für alle ${\displaystyle n}$ schneller als Heapsort und für ${\displaystyle n>80}$ schneller als Quicksort. Etwa bei ${\displaystyle n=10000}$ wird es doppelt so schnell wie Quicksort.[1]

Wegen d​es Klassifizierungsprozesses i​st Flashsort n​icht stabil.

Abgrenzung

Der v​on Neubert a​ls Flashsort vorgestellte Algorithmus h​at den gleichen Namen w​ie ein älterer randomisierter Sortieralgorithmus für parallele Rechnerarchitekturen.[4][5][6]

Siehe auch

• Bucketsort
• Insertionsort

Einzelnachweise

1. Karl-Dietrich Neubert: The Flashsort Algorithm. In: Dr. Dobb's Journal. Februar 1998, S. 123. Abgerufen am 6. November 2007.
2. 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

• 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.uk – ohne 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.

Weblinks

• Flashsort-Seite von Neubert
• Visualization of Flashsort (englisch)