Dynamisches Array of Integer sortieren: welches Sortierverfahren???

[MStoll]

Hi,

wie Medium gesagt hat: es kommt auf Annahmen an, die du zu deinen Daten treffen kannst. QuickSort gilt allgemeinhin als das schnellste, vergleichsbasierte (!) (Einzel-)Verfahren mit einer Laufzeitkomplexität von O(nlogn). Wenn du einen diskreten Wertebereich hast (z.B. Ganzzahlen in festen Grenzen), dann kannst du andere, nicht vergleichsbasierte Verfahren verwenden, die dann in linearer Zeit arbeiten.

Einen Ansatz QuickSort zu verbessern, ist, bei der Rekursion und kleinen Teilmengen der Daten auf ein anderes, "einfacheres" Verfahren zu wechseln, da ein solches oft bei kleinen Datenmengen effizienter ist. In vielen Texten über Algorithmen wird Insertion-Sort vorgeschlagen, mein persönlicher Favorit in diesem Fall ist ShellSort. Dazu könnte man noch Heapsort oder MergeSort als Fallback für den Worst-Case von QuickSort, nämlich O(n^2), implementieren, aber das geht jetzt wohl zu weit von deinem Problem weg.

In deinem Fall, da die Werte zwischen 1 und 128 liegen, solltest du dir Radixsort oder Abwandlungen davon anschauen und einfach mal exemplarisch bestimmen, ob das oder ein vergleichsbasiertes Verfahren schneller ist. Denn bei solch kleinen Datenmengen sagt die asymptotische Laufzeitkomplexität nur wenig über die tatsächlichen Geschwindigkeitsunterschiede aus.

Gruß
Michael