Bibliographic Metadata

Title
Vergleich und Analyse von Partitionierungsalgorithmen für Quicksort / Stephan Beer
Additional Titles
Comparison and analysis of partitioning algorithms for Quicksort
AuthorBeer, Stephan
CensorPanholzer, Alois
PublishedWien, 2018
Description105 Seiten : Diagramme
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2018
Annotation
Zusammenfassung in englischer Sprache
Annotation
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
LanguageGerman
Document typeThesis (Diplom)
Keywords (DE)Quicksort / Dual-Pivot / Sortieren / Average Case-Analyse
Keywords (EN)Quicksort / Dual-Pivot / Sorting / Avereage Case-Analysis
URNurn:nbn:at:at-ubtuw:1-116592 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Vergleich und Analyse von Partitionierungsalgorithmen für Quicksort [1.3 mb]
Links
Reference
Classification
Abstract (German)

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.

Abstract (English)

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.

Stats
The PDF-Document has been downloaded 12 times.