Analyse von Pivotwahlstrategien bei Quicksort

Abstract

Sortieren ist ein grundlegendes Problem der Informatik und es existieren viele bekannte Sortieralgorithmen. Der wohl meistgenutzte Algorithmus ist Quicksort, ein rekursiver in-place Algorithmus, welcher nach dem Divide and Conquer Prinzip arbeitet. Die Eingabe des Algorithmus wird durch die Wahl eines Pivotelements aufgeteilt. Hierbei werden alle Elemente, die kleiner als das Pivotelement sind, links platziert und alle Elemente die größeren sind rechts. Nun wird der Algorithmus erneut aufgerufen, einmal mit dem linken Teil der Eingabe und einmal mit dem rechten Teil. Dies geschieht rekursiv, bis die Eingabe vollständig sortiert ist. In dieser Arbeit werden verschiedene Methoden zu Partitionierung und Pivotwahl in einem C++ Framework implementiert und getestet. Es wird außerdem untersucht, ob es von Vorteil ist, das Verfahren abhängig von der Eingabegröße zu wechseln. Zusätzlich werden die Auswirkungen von Randomisierung und der Inklusion des Pivotelements getestet. Für manche Pivotwahlen werden verschiedene Worst Case Eingaben getestet und untersucht. Alle Ergebnisse werden statistisch ausgewertet. Es hat sich herausgestellt, dass die Hoare Partitionierung generell deutlich besser performt als die Lomuto Partitionierung. Bei kleinen Eingabegrößen sollte Median aus 3 benutzt werden, da dies realtiv sicher gegen schlechte Eingaben ist und trotzdem gut performt. Für große Eingaben schneidet Tukeys Ninther hinsichtlich der Laufzeit und Anzahl an Vergleichen am besten ab. Zusätzlich sollte ab einer Größe von 100-200 auf Median aus 3 zurückfallen und ab Eingabegrößen kleiner 10 auf Insertion Sort. Die Inklusion des Pivotelements sowie die Randomisierung konnten hier keinen Vorteil zeigen.