Mengapa introsort menggunakan heapsort daripada mergesort?

Sebagai bagian dari tugas pekerjaan rumah yang mencakup implementasi introsort saya ditanya mengapa heapsort digunakan daripada algoritma mergesort (atau lainnya dalam hal ini. $O(n\log(n))$

Introsort adalah algoritma pengurutan hibrida yang memberikan kinerja rata-rata cepat dan (terburuk) kinerja kasus terburuk yang optimal. Ini dimulai dengan quicksort dan beralih ke heapsort ketika kedalaman rekursi melebihi level berdasarkan (logaritma) jumlah elemen yang diurutkan. ( Wikipedia , diambil 2014-Mei-06.)

Satu-satunya alasan yang bisa saya pikirkan adalah heapsort "ada di tempat" ... Tapi tbh saya tidak begitu mengerti mengapa ini penting di sini.

algorithms algorithm-analysis sorting pengguna672009
sumber

Jika introsort adalah bagian dari pertanyaan, Anda harus memberi tahu kami apa itu sebelum kami dapat mengatakan apa pun.

Louis

Selamat Datang di Ilmu Komputer ! Perhatikan bahwa Anda dapat menggunakan LaTeX di sini untuk mengeset matematika dengan cara yang lebih mudah dibaca. Lihat di sini untuk pengantar singkat.

FrankW

Kami hanya diminta untuk membuat beberapa kode pseudo untuk pengurutan intro dan kemudian kami ditanya mengapa ia menggunakan heapsort daripada mergesort.

user672009

@ user672009 Dalam hal ini, tuliskan kode untuk keduanya dan lihat apa yang Anda temukan. Alasannya mungkin atau mungkin tidak terkait dengan kinerja.

Raphael

Saya telah menyimpulkan bahwa sejak quicksort mengurutkan di tempat kita perlu menggunakan algoritma pengurutan di tempat lain. Namun saya terbuka untuk input.

user672009

Jawaban:

2 kelemahan Quicksort adalah bahwa ia membutuhkan ruang ekstra (untuk menjaga interval yang tidak disortir) dan pemilihan pivot yang buruk (atau urutan yang dirancang untuk membuat Anda memilih pivot yang buruk) dapat menyebabkannya menjadi waktu dan algoritma ruang ekstra. $O(\log n)$ $O(n^2)$ $O(n)$

Beralih ke heapsort ketika kedalaman rekursi menjadi terlalu besar (di sekitar ) berarti kami memiliki upperbound yang dijamin yaitu waktu dan ruang ekstra. $\log n$ $O(n \log n )$ $O( \log n)$

Heapsort's kebutuhan ruang tambahan membuatnya menjadi pilihan yang lebih baik untuk mergsort's mana untuk array yang dibuat yang masih bisa besar. $O(1)$ $O(n)$ $n$

Alasan heapsort tidak digunakan untuk pengurutan penuh adalah karena lebih lambat daripada quicksort (sebagian karena konstanta tersembunyi dalam ekspresi O besar dan sebagian karena perilaku cache)

aneh ratchet
sumber

Tapi heapsort digunakan ... dan saya curiga itu karena ada di tempat seperti quicksort.

user672009

Saya menduga bahwa @ user672009 bingung dengan kalimat terakhir Anda. Saya sarankan mengklarifikasi bahwa introsort tidak dimulai dengan heapsort karena lebih lambat.

Logika Pengembaraan

O (1)

$O(1)$

O (\lg n)

$O(\lg n)$

Selain itu, heapsort memiliki lebih banyak kesalahan cache daripada introsort.

noɥʇʎԀʎzɐɹƆ

Implementasi Quicksort yang baik tidak membutuhkan ruang O (n) dalam kasus terburuk, asalkan ia mengingat subinterval yang lebih besar pada stack, dan segera menangani yang lebih kecil.

gnasher729