Schnell sortieren vs radix sort

Question

In einer Codierprüfung wurde ich einmal diese Frage gestellt:

Angenommen, Sie sind nur nur Sortierzähne in aufsteigender Reihenfolge, mit welchen Algorithmus Sie verwenden, wenn Sie die Geschwindigkeit am meisten priorisieren möchten, aber Sie möchten auch Platz speichern?

Die Optionen waren:

.
• lsd radix sort
• Merge Sort
• Schnell sortieren

Ich denke, ein Argument kann zwischen lsd radix sort und quicksort gemacht werden.

radix sort würde in $ o (kN) $ und quicksort funktionieren in $ o (n \ log n) $ und schlechteste Fall, $ o (n ^ 2) $

Ich entschied mich für Radix Sort als Antwort, aber ich bin neugierig, was andere sagen müssten.

Answer 1

Dies hängt davon ab, wenn die Anzahl der Eingabennummern $ N $ ist, und übernimmt das Word-RAM-Modell der Berechnung, ein Wortgröße von $ \ theta (\ log n) $ Bits und Worst-Case-Eingaben:

• RADIX SORT würde erforderlich sein $ o (n \ log n) $ Uhrzeit und $ o (n) $ Hilfsraum.

• Quicksort mit fester oder zufälliger Pivot-Selektion würde erforderlich sein $ O (N ^ 2) $ Worst-Case-Zeit und $ O (\ log n) $ Hilfsraum.

• Mergesort erfordert $ O (n \ log n) $ Zeit und $ o (n) $ < / Span> Hilfsraum.

RADIX-Sortier- und Zusammenführungssort entsprechen dann in dieser Einstellung.

Beachten Sie, dass die Verwendung von QuickSort mit zufälliger Pivoit-Auswahl führt zu einer Zeitkomplexität von $ o (n \ log n) $ mit hoher Wahrscheinlichkeit. Auswählen des Pivots deterministisch in einer Weise, die die Elemente in zwei Sets unterteilt, deren Kardinalitäten höchstens ein konstantes Faktor auseinander sind, gibt Ihnen einen Algorithmus mit der Worst-Case-Zeitkomplexität von $ o (n \ log n) $ und $ o (\ log n) $ Hilfsraum.