<div class="csl-bib-body">
<div class="csl-entry">Beer, S. (2018). <i>Vergleich und Analyse von Partitionierungsalgorithmen für Quicksort</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2018.41182</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2018.41182
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/7031
-
dc.description
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
-
dc.description.abstract
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
dc.description.abstract
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
dc.language
Deutsch
-
dc.language.iso
de
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Quicksort
de
dc.subject
Dual-Pivot
de
dc.subject
Sortieren
de
dc.subject
Average Case-Analyse
de
dc.subject
Quicksort
en
dc.subject
Dual-Pivot
en
dc.subject
Sorting
en
dc.subject
Avereage Case-Analysis
en
dc.title
Vergleich und Analyse von Partitionierungsalgorithmen für Quicksort
de
dc.title.alternative
Comparison and analysis of partitioning algorithms for Quicksort
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2018.41182
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Stephan Beer
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie