apa kelebihan heapsort dibanding smoothsort?

8

Wikipedia menyatakan bahwa kelebihan smoothsort daripada heapsort adalah bahwa pada waktu itu mendekati waktu O (n).

Sekarang saya bertanya-tanya apa kelebihan heapsort dibanding smoothsort?

Atau untuk mengulangi pertanyaan ini, apakah smoothsort selalu merupakan pilihan yang lebih baik daripada heapsort (bahkan jika inputnya belum diurutkan ke tingkat apa pun)?

ds.algorithms sorting Pacerier
sumber
Sudahkah Anda membandingkan implementasi? Mungkin perbedaannya adalah smoothsort memiliki overhead yang lebih besar baik dari segi waktu eksekusi dan memori yang digunakan.
Dave Clarke
8
Di heapsort, Anda dapat membangun heap dalam waktu O (n), sementara di smoothsort, O (n log n) membutuhkan waktu untuk membangun heaport. Ini menunjukkan (tetapi tidak menyiratkan) bahwa waktu untuk mengurutkan input acak mungkin lebih lama untuk smoothsort.
Peter Shor
@DaveClarke Maksud saya bukan dalam implementasi (yang dapat bervariasi) tetapi dalam algoritma itu sendiri
Pacerier
@PeterShor Anda yakin perlu O (n log n) untuk membangun heap di smoothsort? Tampaknya akan terbang di hadapan klaim bahwa smoothsort adalah O (n) ketika input sudah diurutkan?
Paul Wagland
1
@PeterShor: Varian smoothsort yang menggunakan daftar biner miring karena hutan tumpukan dapat ditumpuk dalam waktu O (n). Untuk melakukan ini, ubah panjang input menjadi miring biner (O (log (n)). Bit dari angka ini memberi tahu Anda ukuran tumpukan di hutan. Berpura-pura hutan seperti itu sudah ada belum memiliki properti tumpukan. Ini mirip dengan heapsort dengan berpura-pura Anda sudah memiliki heap tanpa properti heap. Namun, bahkan dengan perubahan ini, smoothsort (menggunakan skew biner) hanya lebih cepat daripada heapsort untuk 10% atau kurang disortir (menggunakan inversi ke unsort).
ScootyPuff

Jawaban:

10

Baru saja melakukan beberapa pembacaan pada kedua algoritma, akan terlihat bahwa heapsort tidak memiliki keuntungan O implisit atas smoothsort. Jenis ini masuk akal ketika Anda berpikir bahwa smoothsort hanyalah sejenis heapsort khusus, menggunakan heaport jenis khusus.

Di mana heapsort memiliki kelebihan adalah lebih mudah dipahami, dan didokumentasikan dengan lebih baik. Ada sangat sedikit implementasi smoothsort yang tersedia untuk umum, dan sangat sedikit literatur tentangnya, namun ada banyak literatur tentang heapsort.

Memang, literatur diakses hanya nyata adalah ini menulis-up oleh Keith Schwarz. Ini juga merupakan dasar dari artikel wikipedia .

Paul Wagland
sumber