it-swarm-id.com

Mengapa quicksort lebih baik daripada mergesort?

Saya ditanya pertanyaan ini selama wawancara. Keduanya O(nlogn) namun sebagian besar orang menggunakan Quicksort alih-alih Mergesort. Mengapa demikian?

344

Quicksort memiliki O (n2) runtime kasus terburuk dan O (ncatatann) runtime kasus rata-rata. Namun, lebih baik menggabungkan beberapa skenario karena banyak faktor memengaruhi runtime suatu algoritma, dan, ketika menggabungkan semuanya, quicksort menang.

Secara khusus, runtime algoritma sorting yang sering dikutip merujuk pada jumlah perbandingan atau jumlah swap yang diperlukan untuk melakukan pengurutan data. Ini memang ukuran kinerja yang baik, terutama karena tidak tergantung pada desain perangkat keras yang mendasarinya. Namun, hal-hal lain - seperti lokalitas referensi (mis. Apakah kita membaca banyak elemen yang mungkin ada dalam cache?) - juga memainkan peran penting pada perangkat keras saat ini. Quicksort khususnya membutuhkan sedikit ruang tambahan dan menunjukkan lokasi cache yang bagus, dan ini membuatnya lebih cepat daripada menggabungkan sortir dalam banyak kasus.

Selain itu, sangat mudah untuk menghindari jangka waktu terburuk dari quicksort dari O (n2) hampir seluruhnya dengan menggunakan pilihan pivot yang sesuai - seperti mengambilnya secara acak (ini adalah strategi yang sangat baik).

Dalam praktiknya, banyak implementasi modern quicksort (khususnya libstdc ++'s std::sort) sebenarnya introsort , yang teoretis kasus terburuknya adalah O (ncatatann), sama dengan jenis gabungan. Ini mencapai ini dengan membatasi kedalaman rekursi, dan beralih ke algoritma yang berbeda ( heapsort ) setelah melebihi logn.

258
Konrad Rudolph

Seperti yang dicatat oleh banyak orang, kinerja case rata-rata untuk quicksort lebih cepat daripada mergesort. Tapi ini hanya benar jika Anda mengasumsikan waktu yang konstan untuk mengakses bagian memori yang diminta.

Dalam RAM asumsi ini umumnya tidak terlalu buruk (tidak selalu benar karena cache, tetapi itu tidak terlalu buruk). Namun jika struktur data Anda cukup besar untuk hidup di disk, lalu quicksort terbunuh oleh fakta bahwa disk rata-rata Anda melakukan sesuatu seperti 200 pencarian acak per detik . Tetapi disk yang sama tidak memiliki masalah membaca atau menulis megabyte per detik data secara berurutan. Itulah tepatnya yang dilakukan mergesort.

Karena itu jika data harus diurutkan pada disk, Anda benar-benar ingin menggunakan beberapa variasi pada mergesort. (Umumnya Anda quicksort sublists, lalu mulai menggabungkan mereka bersama di atas beberapa ambang batas ukuran.)

Lebih jauh lagi jika Anda harus melakukan apa pun dengan kumpulan data sebesar itu, pikirkan keras tentang cara menghindari mencari ke disk. Sebagai contoh, inilah alasan mengapa Anda menjatuhkan indeks sebelum melakukan banyak data dalam database, dan kemudian membangun kembali indeks nanti. Mempertahankan indeks selama memuat berarti terus mencari ke disk. Sebaliknya jika Anda menjatuhkan indeks, maka database dapat membangun kembali indeks dengan terlebih dahulu menyortir informasi yang akan ditangani (menggunakan mergesort tentu saja!) Dan kemudian memuatnya ke dalam struktur data BTREE untuk indeks. (BTREE secara alami disimpan dalam urutan, sehingga Anda dapat memuat satu dari dataset yang diurutkan dengan beberapa upaya untuk disk.)

Ada beberapa kesempatan di mana memahami bagaimana cara menghindari disk telah membuat saya melakukan pekerjaan pemrosesan data lebih lama daripada berhari-hari atau berminggu-minggu.

275
user11318

Sebenarnya, QuickSort adalah O (n2). kasus rata-rata waktu berjalannya adalah O (nlog (n)), tetapi kasus terburuk adalah O (n2), yang terjadi ketika Anda menjalankannya pada daftar yang berisi beberapa item unik. Pengacakan mengambil O (n). Tentu saja, ini tidak mengubah kasus terburuknya, itu hanya mencegah pengguna jahat membuat penyortiran Anda memakan waktu lama.

QuickSort lebih populer karena:

  1. Ada di tempat (MergeSort membutuhkan memori tambahan linier ke sejumlah elemen yang akan diurutkan).
  2. Memiliki konstanta tersembunyi kecil.
88
Dark Shikari

"Namun kebanyakan orang menggunakan Quicksort alih-alih Mergesort. Mengapa begitu?"

Salah satu alasan psikologis yang belum diberikan adalah Quicksort diberi nama lebih pintar. yaitu pemasaran yang baik.

Ya, Quicksort dengan triple partioning mungkin adalah salah satu dari algoritma pengurutan tujuan umum terbaik, tetapi tidak ada fakta bahwa jenis "Cepat" terdengar jauh lebih kuat daripada jenis "Gabungkan".

29
Ash

Seperti yang telah dicatat orang lain, kasus terburuk Quicksort adalah O (n ^ 2), sedangkan mergesort dan heapsort tetap di O (nlogn). Namun, pada kasus rata-rata, ketiganya adalah O (nlogn); jadi mereka untuk sebagian besar kasus sebanding.

Apa yang membuat Quicksort lebih baik secara rata-rata adalah bahwa loop internal menyiratkan membandingkan beberapa nilai dengan satu nilai, sedangkan pada dua lainnya kedua istilah berbeda untuk setiap perbandingan. Dengan kata lain, Quicksort membaca setengah dari dua algoritma lainnya. Pada CPU modern, kinerja sangat didominasi oleh waktu akses, sehingga pada akhirnya Quicksort akhirnya menjadi pilihan pertama yang bagus.

15
Javier

Saya ingin menambahkan bahwa dari ketiga algoritma yang disebutkan sejauh ini (mergesort, quicksort dan heap sort) hanya mergesort yang stabil. Artinya, urutannya tidak berubah untuk nilai-nilai yang memiliki kunci yang sama. Dalam beberapa kasus ini diinginkan.

Tapi, jujur ​​saja, dalam situasi praktis kebanyakan orang hanya membutuhkan kinerja rata-rata yang baik dan quicksort adalah ... quick =)

Semua jenis algoritma mengalami pasang surut. Lihat artikel Wikipedia untuk algoritme pengurutan untuk ikhtisar yang bagus.

8
Antti Rasinen

Dari entri Wikipedia pada Quicksort :

Quicksort juga bersaing dengan mergesort, algoritma pengurutan rekursi lain tetapi dengan manfaat waktu berjalan Θ (nlogn) terburuk. Mergesort adalah jenis yang stabil, tidak seperti quicksort dan heapsort, dan dapat dengan mudah diadaptasi untuk beroperasi pada daftar yang ditautkan dan daftar yang sangat besar disimpan pada media yang aksesnya lambat seperti penyimpanan disk atau penyimpanan yang terhubung dengan jaringan. Meskipun quicksort dapat ditulis untuk beroperasi pada daftar yang ditautkan, ia sering menderita pilihan pivot yang buruk tanpa akses acak. Kerugian utama dari mergesort adalah bahwa, ketika beroperasi pada array, ia memerlukan Θ (n) ruang tambahan dalam kasus terbaik, sedangkan varian quicksort dengan partisi di tempat dan rekursi ekor hanya menggunakan ruang Θ (logn). (Perhatikan bahwa ketika beroperasi pada daftar yang ditautkan, mergesort hanya membutuhkan sejumlah kecil penyimpanan tambahan.)

7
gnobal

Mu! Quicksort tidak lebih baik, ini cocok untuk jenis aplikasi yang berbeda, daripada mergesort.

Mergesort patut dipertimbangkan jika kecepatan adalah hal yang paling penting, kinerja kasus terburuk tidak dapat ditoleransi, dan ruang tambahan tersedia . 1

Anda menyatakan bahwa mereka "Keduanya O(nlogn) [...]". Ini salah. "Quicksort menggunakan perbandingan sekitar n ^ 2/2 dalam kasus terburuk." 1 .

Namun properti paling penting menurut pengalaman saya adalah implementasi mudah dari akses sekuensial yang dapat Anda gunakan saat menyortir saat menggunakan bahasa pemrograman dengan paradigma imperatif.

1 Sedgewick, Algoritma

7
Roman Glass

Quicksort adalah algoritma penyortiran tercepat dalam praktiknya tetapi memiliki sejumlah kasus patologis yang dapat membuatnya berkinerja seburuk O (n2).

Heapsort dijamin berjalan di O (n * ln (n)) dan hanya membutuhkan penyimpanan tambahan yang terbatas. Tetapi ada banyak kutipan tes dunia nyata yang menunjukkan bahwa heapsort secara signifikan lebih lambat daripada quicksort rata-rata.

6
Niyaz

Penjelasan Wikipedia adalah:

Biasanya, quicksort secara signifikan lebih cepat dalam praktik daripada algoritma Θ (nlogn) lainnya, karena loop dalamnya dapat diimplementasikan secara efisien pada sebagian besar arsitektur, dan dalam sebagian besar data dunia nyata dimungkinkan untuk membuat pilihan desain yang meminimalkan kemungkinan membutuhkan waktu kuadratik .

Quicksort

Mergesort

Saya pikir ada juga masalah dengan jumlah penyimpanan yang dibutuhkan untuk Mergesort (yaitu Ω (n)) yang tidak dimiliki oleh implementasi quicksort. Dalam kasus terburuk, mereka memiliki jumlah waktu algoritmik yang sama, tetapi mergesort membutuhkan lebih banyak penyimpanan.

5
Mat Mannion

Saya ingin menambahkan ke jawaban yang ada beberapa matematika tentang bagaimana QuickSort melakukan ketika menyimpang dari kasus terbaik dan seberapa besar kemungkinannya, yang saya harap akan membantu orang memahami sedikit lebih baik mengapa kasus O (n ^ 2) tidak nyata keprihatinan dalam implementasi QuickSort yang lebih canggih.

Di luar masalah akses acak, ada dua faktor utama yang dapat memengaruhi kinerja QuickSort dan keduanya terkait dengan bagaimana pivot dibandingkan dengan data yang diurutkan.

1) Sejumlah kecil kunci dalam data. Dataset semua nilai yang sama akan mengurutkan n ^ 2 kali pada QuickSort 2 partisi Vanilla karena semua nilai kecuali lokasi pivot ditempatkan di satu sisi setiap kali. Implementasi modern mengatasi ini dengan metode seperti menggunakan semacam 3-partisi. Metode-metode ini dieksekusi pada dataset dengan nilai yang sama dalam waktu O(n). Jadi menggunakan implementasi seperti itu berarti bahwa input dengan sejumlah kecil kunci sebenarnya meningkatkan waktu kinerja dan tidak lagi menjadi perhatian.

2) Pilihan pivot yang sangat buruk dapat menyebabkan kinerja kasus terburuk. Dalam kasus yang ideal, pivot akan selalu sedemikian rupa sehingga 50% data lebih kecil dan 50% data lebih besar, sehingga input akan dibagi dua selama setiap iterasi. Ini memberi kita n perbandingan dan swap kali log-2 (n) rekursi untuk waktu O (n * logn).

Berapa pengaruh pemilihan pivot yang tidak ideal mempengaruhi waktu eksekusi?

Mari kita perhatikan kasus di mana pivot dipilih secara konsisten sehingga 75% data berada di satu sisi pivot. Ini masih O (n * logn) tetapi sekarang basis log telah berubah menjadi 1/0,75 atau 1,33. Hubungan dalam kinerja ketika mengubah basis selalu merupakan konstanta yang diwakili oleh log (2)/log (newBase). Dalam hal ini, konstanta itu adalah 2.4. Jadi kualitas pivot pilihan ini membutuhkan waktu 2,4 kali lebih lama dari yang ideal.

Seberapa cepat ini menjadi lebih buruk?

Tidak terlalu cepat sampai pilihan pivot menjadi (konsisten) sangat buruk:

  • 50% di satu sisi: (kasus ideal)
  • 75% di satu sisi: 2,4 kali lebih lama
  • 90% di satu sisi: 6,6 kali lebih lama
  • 95% di satu sisi: 13,5 kali lebih lama
  • 99% di satu sisi: 69 kali lebih lama

Saat kami mendekati 100% di satu sisi, bagian log dari eksekusi mendekati n dan keseluruhan eksekusi mendekati O (n ^ 2).

Dalam implementasi QuickSort yang naif, kasus seperti array yang diurutkan (untuk pivot elemen 1) atau array yang diurutkan terbalik (untuk pivot elemen terakhir) akan menghasilkan waktu eksekusi O (n ^ 2) terburuk. Selain itu, implementasi dengan pemilihan pivot yang dapat diprediksi dapat dikenai serangan DoS oleh data yang dirancang untuk menghasilkan eksekusi kasus terburuk. Implementasi modern menghindari ini dengan berbagai metode, seperti mengacak data sebelum mengurutkan, memilih median dari 3 indeks yang dipilih secara acak, dll. Dengan pengacakan ini dalam campuran, kami memiliki 2 kasus:

  • Kumpulan data kecil. Kasus terburuk cukup mungkin tetapi O (n ^ 2) tidak bersifat bencana karena n cukup kecil sehingga n ^ 2 juga kecil.
  • Kumpulan data besar. Kasus terburuk adalah mungkin secara teori tetapi tidak dalam praktiknya.

Seberapa besar kemungkinan kita melihat kinerja yang buruk?

Peluangnya adalah semakin kecil . Mari kita pertimbangkan semacam 5.000 nilai:

Implementasi hipotetis kami akan memilih pivot menggunakan median 3 indeks yang dipilih secara acak. Kami akan menganggap pivot yang berada dalam kisaran 25% -75% sebagai "baik" dan pivot yang berada dalam kisaran 0% -25% atau 75% -100% sebagai "buruk". Jika Anda melihat distribusi probabilitas menggunakan median 3 indeks acak, setiap rekursi memiliki peluang 11/16 untuk berakhir dengan poros yang baik. Mari kita membuat 2 asumsi konservatif (dan salah) untuk menyederhanakan matematika:

  1. Pivot yang baik selalu tepat pada pemisahan 25%/75% dan beroperasi pada kasus ideal 2,4 *. Kami tidak pernah mendapatkan pemecahan yang ideal atau pemecahan yang lebih baik dari 25/75.

  2. Pivot buruk selalu merupakan kasus terburuk dan pada dasarnya tidak berkontribusi apa pun pada solusi.

Implementasi QuickSort kami akan berhenti di n = 10 dan beralih ke jenis penyisipan, jadi kami membutuhkan 22 25%/75% partisi pivot untuk memecah 5.000 input nilai turun sejauh itu. (10 * 1.333333 ^ 22> 5000) Atau, kami membutuhkan 4990 pivot terburuk. Ingatlah bahwa jika kita mengakumulasikan 22 pivot yang baik pada titik mana pun maka pengurutan akan selesai, jadi kasus terburuk atau apa pun di dekatnya memerlukan sangat nasib buruk. Jika kami membutuhkan 88 rekursi untuk benar-benar mencapai 22 pivot yang baik yang diperlukan untuk mengurutkan ke n = 10, itu akan menjadi 4 * 2.4 * kasus ideal atau sekitar 10 kali waktu pelaksanaan kasus ideal. Seberapa besar kemungkinan bahwa kita tidak mencapai 22 pivot baik yang diperlukan setelah 88 rekursi?

distribusi probabilitas binomial dapat menjawabnya, dan jawabannya adalah sekitar 10 ^ -18. (n adalah 88, k adalah 21, p adalah 0.6875) Pengguna Anda sekitar seribu kali lebih mungkin tersambar petir dalam 1 detik yang dibutuhkan untuk mengklik [SORT] daripada melihat 5.000 item yang dijalankan lebih buruk dari 10 * kasus ideal. Peluang ini semakin kecil karena dataset semakin besar. Berikut adalah beberapa ukuran array dan peluang terkait untuk berjalan lebih dari 10 * ideal:

  • Array yang terdiri dari 640 item: 10 ^ -13 (membutuhkan 15 poin pivot baik dari 60 percobaan)
  • Array 5.000 item: 10 ^ -18 (membutuhkan 22 pivot yang baik dari 88 percobaan)
  • Array terdiri dari 40.000 item: 10 ^ -23 (membutuhkan 29 pivot yang baik dari 116)

Ingatlah bahwa ini dengan 2 asumsi konservatif yang lebih buruk daripada kenyataan. Jadi kinerja aktual lebih baik, dan keseimbangan dari probabilitas yang tersisa lebih dekat ke ideal daripada tidak.

Akhirnya, seperti yang telah disebutkan orang lain, bahkan kasus yang tidak masuk akal ini dapat dihilangkan dengan beralih ke tumpukan jika tumpukan rekursi terlalu dalam. Jadi TLDR adalah bahwa, untuk implementasi QuickSort yang baik, kasus terburuk tidak benar-benar ada karena telah direkayasa dan eksekusi selesai dalam waktu O (n * logn).

4
Lance Wisely

Quicksort TIDAK lebih baik dari mergesort. Dengan O (n ^ 2) (kasus terburuk yang jarang terjadi), quicksort berpotensi jauh lebih lambat daripada O(nlogn) dari jenis gabungan. Quicksort memiliki lebih sedikit overhead, jadi dengan n kecil dan komputer lambat, lebih baik. Tetapi komputer sangat cepat hari ini sehingga overhead tambahan dari mergesort dapat diabaikan, dan risiko quicksort yang sangat lambat jauh melebihi biaya overhead yang tidak signifikan dari mergesort dalam banyak kasus.

Selain itu, mergesort meninggalkan item dengan kunci identik dalam urutan aslinya, atribut yang berguna.

4
xpda

Mengapa Quicksort bagus?

  • QuickSort mengambil N ^ 2 dalam kasus terburuk dan rata-rata NlogN. Kasus terburuk terjadi ketika data diurutkan. Ini dapat dikurangi dengan acak acak sebelum penyortiran dimulai.
  • QuickSort tidak membutuhkan memori ekstra yang diambil berdasarkan penggabungan.
  • Jika dataset besar dan ada item yang identik, kompleksitas Quicksort berkurang dengan menggunakan partisi 3 arah. Lebih banyak item identik tidak lebih baik semacam itu. Jika semua item identik, itu semacam waktu linier. [Ini adalah implementasi default di sebagian besar perpustakaan]

Apakah Quicksort selalu lebih baik daripada Mergesort?

Tidak juga.

  • Mergesort stabil tetapi Quicksort tidak. Jadi jika Anda membutuhkan stabilitas dalam output, Anda akan menggunakan Mergesort. Stabilitas diperlukan dalam banyak aplikasi praktis.
  • Memori murah saat ini. Jadi jika memori tambahan yang digunakan oleh Mergesort tidak penting untuk aplikasi Anda, tidak ada salahnya menggunakan Mergesort.

Catatan: Di Jawa, fungsi Arrays.sort () menggunakan Quicksort untuk tipe data primitif dan Mergesort untuk tipe data objek. Karena objek mengkonsumsi overhead memori, jadi menambahkan sedikit overhead untuk Mergesort mungkin bukan masalah untuk sudut pandang kinerja.

Referensi : Tonton video QuickSort Minggu 3, Kursus Algoritma Princeton di Coursera

4

Tidak seperti Merge Sort Quick Sort tidak menggunakan ruang tambahan. Sedangkan Gabung Sortir menggunakan ruang bantu O (n). Tetapi Gabung Urut memiliki kompleksitas waktu kasus terburuk dari O(nlogn) sedangkan kompleksitas kasus terburuk dari Urutkan Cepat adalah O (n ^ 2) yang terjadi ketika array sudah diurutkan.

3
Shantam Mittal

Jawabannya akan sedikit condong ke quicksort dengan perubahan yang dibawa dengan DualPivotQuickSort untuk nilai primitif. Ini digunakan dalam Java 7 untuk mengurutkan Java.util.Arrays

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

Anda dapat menemukan implementasi Java7 di sini - http://grepcode.com/file/repository.grepcode.com/Java/root/jdk/openjdk/7-b147/Java/util/Arrays.Java

Bacaan Luar Biasa Lebih Lanjut tentang DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.Java.openjdk.core-libs.devel/2628

3
appbootup

Dalam merge-sort, algoritma umum adalah:

  1. Sortir sub-array kiri
  2. Sortir sub-array yang tepat
  3. Gabungkan 2 sub-array yang diurutkan

Di tingkat atas, menggabungkan 2 sub-array yang diurutkan melibatkan berurusan dengan elemen N.

Satu tingkat di bawahnya, setiap iterasi dari langkah 3 melibatkan berurusan dengan elemen N/2, tetapi Anda harus mengulangi proses ini dua kali. Jadi Anda masih berurusan dengan 2 * N/2 == elemen N.

Satu tingkat di bawahnya, Anda menggabungkan 4 * N/4 == elemen N, dan seterusnya. Setiap kedalaman dalam tumpukan rekursif melibatkan penggabungan jumlah elemen yang sama, di semua panggilan untuk kedalaman itu.

Pertimbangkan algoritma penyortiran cepat sebagai gantinya:

  1. Pilih titik pivot
  2. Tempatkan titik pivot di tempat yang benar dalam array, dengan semua elemen yang lebih kecil di sebelah kiri, dan elemen yang lebih besar di sebelah kanan
  3. Sortir subarray kiri
  4. Sortir subarray kanan

Di tingkat atas, Anda berurusan dengan array ukuran N. Anda kemudian memilih satu titik pivot, meletakkannya di posisi yang benar, dan kemudian dapat mengabaikannya sepenuhnya untuk sisa algoritma.

Satu tingkat di bawahnya, Anda berurusan dengan 2 sub-array yang memiliki ukuran gabungan N-1 (yaitu, kurangi titik pivot sebelumnya). Anda memilih titik pivot untuk setiap sub-larik, yang muncul hingga 2 poin pivot tambahan.

Satu tingkat di bawahnya, Anda berurusan dengan 4 sub-array dengan ukuran gabungan N-3, untuk alasan yang sama seperti di atas.

Lalu N-7 ... Lalu N-15 ... Lalu N-32 ...

Kedalaman tumpukan rekursif Anda tetap kurang lebih sama (logN). Dengan merge-sort, Anda selalu berurusan dengan gabungan elemen-N, di setiap tingkat tumpukan rekursif. Dengan pengurutan cepat, jumlah elemen yang Anda hadapi berkurang saat Anda pergi ke tumpukan. Misalnya, jika Anda melihat kedalaman di tengah melalui tumpukan rekursif, jumlah elemen yang Anda hadapi adalah N - 2 ^ ((logN)/2)) == N - sqrt (N).

Penafian: Pada penggabungan-penggabungan, karena Anda membagi array menjadi 2 potongan yang sama persis setiap kali, kedalaman rekursif persis logN. Pada penyortiran cepat, karena titik pivot Anda tidak mungkin persis di tengah array, kedalaman tumpukan rekursif Anda mungkin sedikit lebih besar daripada logN. Saya belum melakukan matematika untuk melihat seberapa besar peran faktor ini dan faktor yang dijelaskan di atas, sebenarnya berperan dalam kompleksitas algoritma.

3
RvPr

Quicksort memiliki kompleksitas kasus rata-rata yang lebih baik tetapi dalam beberapa aplikasi itu adalah pilihan yang salah. Quicksort rentan terhadap penolakan serangan layanan. Jika seorang penyerang dapat memilih input yang akan diurutkan, ia dapat dengan mudah membangun set yang mengambil kompleksitas waktu terburuk dari o (n ^ 2).

Kompleksitas kasus rata-rata Mergesort dan kompleksitas kasus terburuk adalah sama, dan karenanya tidak mengalami masalah yang sama. Properti penggabungan-jenis ini juga menjadikannya pilihan terbaik untuk sistem waktu-nyata - tepatnya karena tidak ada kasus patologis yang menyebabkannya berjalan jauh, jauh lebih lambat.

Saya penggemar Mergesort yang lebih besar daripada saya di Quicksort, karena alasan ini.

2
Simon Johnson

Walaupun mereka berdua berada di kelas kompleksitas yang sama, itu tidak berarti mereka berdua memiliki runtime yang sama. Quicksort biasanya lebih cepat daripada mergesort, hanya karena lebih mudah untuk membuat kode implementasi yang ketat dan operasi yang dilakukannya dapat berjalan lebih cepat. Itu karena quicksort itu umumnya lebih cepat sehingga orang menggunakannya daripada mergesort.

Namun! Saya pribadi sering akan menggunakan mergesort atau varian quicksort yang menurun ke mergesort ketika quicksort buruk. Ingat. Quicksort hanya O (n log n) pada rata-rata . Kasus terburuknya adalah O (n ^ 2)! Mergesort selalu O (n log n). Dalam kasus di mana kinerja realtime atau responsif adalah suatu keharusan dan data input Anda dapat berasal dari sumber jahat, Anda tidak boleh menggunakan quicksort biasa.

2
DJ Capelis

Sort cepat adalah case terburuk O (n ^ 2), namun, rata-rata case secara konsisten berkinerja penggabungan. Setiap algoritma adalah O (nlogn), tetapi Anda harus ingat bahwa ketika berbicara tentang Big O kita mengabaikan faktor kompleksitas yang lebih rendah. Penyortiran cepat memiliki peningkatan signifikan terhadap penyatuan penggabungan ketika datang ke faktor konstan.

Penggabungan sortir juga membutuhkan memori O(2n), sementara sortasi cepat dapat dilakukan di tempat (hanya membutuhkan O (n)). Ini adalah alasan lain bahwa sort cepat umumnya lebih disukai daripada sortir gabungan.

Info tambahan:

Kasus penyortiran cepat terburuk terjadi ketika pivot dipilih dengan buruk. Perhatikan contoh berikut:

[5, 4, 3, 2, 1]

Jika pivot dipilih sebagai angka terkecil atau terbesar dalam grup maka pengurutan cepat akan berjalan di O (n ^ 2). Probabilitas memilih elemen yang ada di 25% terbesar atau terkecil dari daftar adalah 0,5. Itu memberikan algoritma peluang 0,5 menjadi pivot yang baik. Jika kami menggunakan algoritma pemilihan pivot pada umumnya (katakanlah memilih elemen acak), kami memiliki 0,5 peluang untuk memilih pivot yang baik untuk setiap pilihan pivot. Untuk koleksi ukuran besar probabilitas selalu memilih poros yang buruk adalah 0,5 * n. Berdasarkan probabilitas ini quick sort efisien untuk kasus rata-rata (dan tipikal).

2
Wade Anderson

Ini adalah pertanyaan yang cukup lama, tetapi karena saya sudah membahas keduanya baru-baru ini, inilah 2c saya:

Gabungkan kebutuhan sortir rata-rata ~ N log N perbandingan. Untuk array yang sudah diurutkan sudah (hampir) diurutkan, ini turun menjadi 1/2 N log N, karena saat menggabungkan kita (hampir) selalu memilih bagian "kiri" 1/2 N kali dan kemudian hanya menyalin kanan elemen 1/2 N. Selain itu saya dapat berspekulasi bahwa input yang sudah diurutkan membuat prediktor cabang prosesor bersinar tetapi menebak hampir semua cabang dengan benar, sehingga mencegah warung pipa.

Sortir cepat rata-rata membutuhkan perbandingan ~ 1,38 N log N. Ini tidak mendapatkan banyak manfaat dari array yang sudah diurutkan dalam hal perbandingan (namun itu dalam hal swap dan mungkin dalam hal prediksi cabang di dalam CPU).

Tolok ukur saya pada prosesor yang cukup modern menunjukkan hal berikut:

Ketika fungsi perbandingan adalah fungsi callback (seperti dalam implementasi qsort () libc) quicksort lebih lambat dari mergesort sebesar 15% pada input acak dan 30% untuk array yang sudah diurutkan untuk bilangan bulat 64 bit.

Di sisi lain jika perbandingan bukan panggilan balik, pengalaman saya adalah bahwa quicksort mengungguli mergesort hingga 25%.

Namun jika array (besar) Anda memiliki nilai unik yang sangat sedikit, penggabungan sortir mulai mendapatkan lebih dari quicksort dalam hal apa pun.

Jadi mungkin intinya adalah: jika perbandingan itu mahal (mis. Fungsi callback, membandingkan string, membandingkan banyak bagian struktur yang sebagian besar mendapatkan "ketiga" keempat-ke-dua) - kemungkinannya adalah Anda akan lebih baik dengan semacam penggabungan. Untuk tugas-tugas sederhana quicksort akan lebih cepat.

Yang mengatakan semua yang dikatakan sebelumnya adalah benar: - Quicksort dapat menjadi N ^ 2, tetapi Sedgewick mengklaim bahwa implementasi acak yang baik memiliki lebih banyak peluang komputer yang melakukan semacam tersambar petir daripada pergi N ^ 2 - Mergesort membutuhkan ruang ekstra

2
virco

Ketika saya bereksperimen dengan kedua algoritma pengurutan, dengan menghitung jumlah panggilan rekursif, quicksort secara konsisten memiliki panggilan rekursif kurang dari mergesort. Itu karena quicksort memiliki pivot, dan pivot tidak termasuk dalam panggilan rekursif berikutnya. Dengan cara itu quicksort dapat mencapai base case rekursif lebih cepat daripada mergesort.

2
Aldian Fazrihady

Tambahan kecil untuk quick vs merge sort.

Juga bisa tergantung pada jenis barang yang disortir. Jika akses ke item, swap dan perbandingan bukan operasi sederhana, seperti membandingkan integer dalam memori pesawat, maka penggabungan sort bisa menjadi algoritma yang lebih disukai.

Misalnya, kami mengurutkan item menggunakan protokol jaringan di server jauh.

Juga, dalam wadah khusus seperti "daftar tertaut", tidak ada untungnya penyortiran cepat.
1. Gabungkan urutkan pada daftar tertaut, tidak perlu memori tambahan. 2. Akses ke elemen dalam sortir cepat tidak berurutan (dalam memori)

1
minorlogic

Itu sulit dikatakan. Yang terburuk dari MergeSort adalah n (log2n) -n + 1, yang akurat jika n sama dengan 2 ^ k (saya sudah membuktikan ini). Dan untuk n apa pun, itu antara (n lg n - n + 1) dan (n lg n + n + O (lg n)). Tetapi untuk quickSort, yang terbaik adalah nlog2n (juga n sama dengan 2 ^ k). Jika Anda membagi Mergesort dengan quickSort, itu sama dengan satu ketika n tidak terbatas. Jadi seolah-olah kasus terburuk dari MergeSort lebih baik daripada kasus QuickSort terbaik, mengapa kita menggunakan quicksort? Tapi ingat, MergeSort tidak ada di tempat, memerlukan ruang 2n memeroy. Dan MergeSort juga perlu melakukan banyak salinan array, yang kami tidak termasuk dalam analisis algoritma. Dalam sebuah Word, MergeSort benar-benar lebih cepat daripada quicksort dalam theroy, tetapi pada kenyataannya Anda perlu mempertimbangkan ruang memeory, biaya array array, merger lebih lambat daripada jenis cepat. Saya pernah membuat Percobaan di mana saya diberi 10.00000 digit dalam Java oleh kelas Acak, dan butuh 2610 ms dengan mergesort, 1370ms dengan quicksort.

1
Peter

Semua hal dianggap sama, saya berharap kebanyakan orang menggunakan apa pun yang paling nyaman tersedia, dan itu cenderung qsort (3). Selain itu quicksort dikenal sangat cepat pada array, seperti halnya mergesort adalah pilihan umum untuk daftar.

Yang saya ingin tahu adalah mengapa sangat jarang untuk melihat radix atau semacam ember. Mereka O (n), setidaknya pada daftar tertaut dan yang diperlukan hanyalah beberapa metode untuk mengubah kunci ke nomor urut. (Senar dan pelampung bekerja dengan baik.)

Saya berpikir alasannya ada hubungannya dengan bagaimana ilmu komputer diajarkan. Saya bahkan harus menunjukkan kepada dosen saya dalam analisis Algoritma bahwa memang mungkin untuk menyortir lebih cepat daripada O (n log (n)). (Dia memiliki bukti bahwa Anda tidak dapat perbandingan mengurutkan lebih cepat daripada O (n log (n)), yang benar.)

Dalam berita lain, float dapat diurutkan sebagai bilangan bulat, tetapi Anda harus mengubah angka negatif setelahnya.

Sunting: Sebenarnya, inilah cara yang lebih ganas untuk menyortir float-as-integers: http://www.stereopsis.com/radix.html . Perhatikan bahwa trik membalik bit dapat digunakan terlepas dari algoritma pengurutan apa yang sebenarnya Anda gunakan ...

1
Anders Eurenius

Pertimbangkan kompleksitas waktu dan ruang keduanya. Untuk Pengurutan gabungan: Kompleksitas waktu: O(nlogn), Kompleksitas ruang: O (nlogn)

Untuk Pengurutan Cepat: Kompleksitas waktu: O (n ^ 2), Kompleksitas ruang: O (n)

Sekarang, mereka berdua menang dalam satu scenerio masing-masing. Tetapi, dengan menggunakan pivot acak Anda hampir selalu dapat mengurangi kompleksitas Waktu dari Quick sort to O (nlogn).

Dengan demikian, Pengurutan cepat lebih disukai di banyak aplikasi daripada Pengurutan gabungan.

0
pankaj

Pengurutan cepat adalah algoritma pengurutan di tempat, jadi lebih cocok untuk array. Penggabungan penggabungan di sisi lain membutuhkan penyimpanan ekstra O (N), dan lebih cocok untuk daftar tertaut.

Tidak seperti array, dalam daftar suka kita dapat menyisipkan item di tengah dengan O(1) spasi dan O(1) waktu, oleh karena itu operasi penggabungan dalam semacam gabungan dapat diimplementasikan tanpa ada ruang ekstra. Namun, mengalokasikan dan menghapus alokasi ruang ekstra untuk array memiliki efek buruk pada waktu run of merge sort. Gabungkan sort juga mendukung daftar tertaut karena data diakses secara berurutan, tanpa banyak akses memori acak.

Pengurutan cepat di sisi lain membutuhkan banyak akses memori acak dan dengan sebuah array kita dapat langsung mengakses memori tanpa melintasi seperti yang diperlukan oleh daftar tertaut. Juga pengurutan cepat ketika digunakan untuk array memiliki lokalitas referensi yang baik karena array disimpan secara bersamaan dalam memori.

Meskipun kedua algoritma pengurutan kompleksitas rata-rata adalah O (NlogN), biasanya orang-orang untuk tugas-tugas biasa menggunakan array untuk penyimpanan, dan untuk alasan itu pengurutan cepat harus menjadi algoritma pilihan.

EDIT: Saya baru saja menemukan bahwa menggabungkan semacam terburuk/terbaik/kasus rata-rata selalu nlogn, tetapi sort cepat dapat bervariasi dari n2 (kasus terburuk ketika elemen sudah diurutkan) ke nlogn (rata-rata/kasus terbaik ketika pivot selalu membagi array menjadi dua. bagian).

0
Saad