Welchen Vorteil hat Heapsort gegenüber Smoothsort?

8

Wikipedia gibt an, dass die Vorteile von Smoothsort gegenüber Heapsort darin bestehen, dass es manchmal näher an der O (n) -Zeit liegt .

Jetzt habe ich mich gefragt, welchen Vorteil Heapsort gegenüber Smoothsort hat.

Oder um diese Frage neu zu formulieren: Ist Smoothsort immer eine bessere Wahl als Heapsort (auch wenn die Eingabe noch nicht zu einem gewissen Grad sortiert ist)?

ds.algorithms sorting Pacerier
quelle
Haben Sie Implementierungen verglichen? Möglicherweise besteht der Unterschied darin, dass Smoothsort sowohl hinsichtlich der Ausführungszeit als auch des verwendeten Speichers einen größeren Overhead hat.
Dave Clarke
8
In Heapsort können Sie den Heap in der Zeit O (n) erstellen, während in Smoothsort die Zeit O (n log n) benötigt wird, um den Heap zu erstellen. Dies deutet darauf hin (impliziert dies jedoch nicht), dass die Zeit zum Sortieren von Zufallseingaben für Smoothsort möglicherweise länger ist.
Peter Shor
@ DaveClarke Ich meine nicht in der Implementierung (die variieren kann), sondern im Algorithmus selbst
Pacerier
@PeterShor Sind Sie sicher, dass O (n log n) erforderlich ist, um den Heap in Smoothsort zu erstellen? Das scheint angesichts der Behauptung, dass Smoothsort O (n) ist, wenn die Eingabe bereits sortiert ist, zu fliegen?
Paul Wagland
1
@PeterShor: Eine Variante von Smoothsort, die eine Skew-Binärliste als Gesamtstruktur von Heaps verwendet, kann in O (n) -Zeit Heapifiziert werden. Konvertieren Sie dazu die Länge der Eingabe in Skew-Binär (O (log (n)). Die Bits dieser Zahl geben die Heap-Größen in der Gesamtstruktur an. Stellen Sie sich vor, eine solche Gesamtstruktur ist bereits vorhanden und verfügt nicht über die Heap-Eigenschaft. Erzwingen Dies ist ähnlich wie bei Heapsort, wenn Sie so tun, als hätten Sie bereits einen Heap ohne die Heap-Eigenschaft. Trotz dieser Änderung ist Smoothsort (unter Verwendung von Skew-Binär) nur für 10% oder weniger unsortiert (unter Verwendung von Inversionen zum Unsortieren) schneller als Heapsort.
ScootyPuff

Antworten:

10

Nach einigem Nachlesen der beiden Algorithmen scheint Heapsort keinen impliziten O- Vorteil gegenüber Smoothsort zu haben. Diese Art von macht Sinn, wenn Sie denken, dass Smoothsort nur eine spezielle Art von Heapsort ist, wobei eine spezielle Art von Heap verwendet wird.

Heapsort hat den Vorteil, dass es leichter zu verstehen und viel besser dokumentiert ist. Es gibt nur sehr wenige öffentlich verfügbare Implementierungen von Smoothsort und nur sehr wenig Literatur dazu, es gibt jedoch viel Literatur zu Heapsort.

In der Tat ist die einzige wirklich zugängliche Literatur dieser Artikel von Keith Schwarz. Es ist auch die Grundlage des Wikipedia-Artikels .

Paul Wagland
quelle