Beer, S. (2018). Vergleich und Analyse von Partitionierungsalgorithmen für Quicksort [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2018.41182
Das Sortieren großer Datenmengen stellt in der Computerwissenschaft seit jeher einen wichtigen Bestandteil dar. Zwei wichtige Eigenschaften werden von Sortieralgorithmen gefordert, Korrektheit und Geschwindigkeit. Seit Jahren ist die von Hoare 1962 entwickelte Quicksort-Familie das De-facto-Standardverfahren. Im Jahr 2009 sorgte allerdings eine Arbeit von Yaroslavskiy für Aufsehen. In dieser wurde gezeigt, dass eine bis dahin vernachlässigte Variante schneller ist als der alte Standard: Das Sortieren mit Hilfe zweier Pivot-Elemente. Diese Arbeit hat sich das Ziel gesetzt, die neuesten Entwicklungen innerhalb dieser Familie zu analysieren und mit den alten Verfahren zu vergleichen. Neben einer ausführlichen theoretischen Analyse werden die betrachteten Verfahren auch praktisch umgesetzt und die benötigten Rechenzeiten verglichen.
de
Sorting big data is one of the most important parts in computer science ever since. Correctness and speed are two key properties each alogrithm requires. Since Hoare presented the quicksort family in 1962 it has been one of the most used algorithms to sort big data sets. In 2009 Vladimir Yaroslavskiy presented a new version of quicksort which completed the task faster than any other version. His work is based on selecting two pivots instead of one, a technique thought to be inferior. The goal of this thesis is to analyse the latest developments within the quicksort family and compare them with older versions. Besides an exact analysis of each algorithm, the algorithms were also implemented and the needed running times were compared.
en
Additional information:
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
