Mengapa quicksort lebih baik daripada mergesort?

Saya ditanya pertanyaan ini saat wawancara. Keduanya O (nlogn) dan kebanyakan orang menggunakan Quicksort, bukan Mergesort. Mengapa demikian?

Quicksort memiliki runtime kasus terburuk O ( n ² ) dan runtime kasus rata-rata O ( n log n ). Namun, lebih baik menggabungkan beberapa skenario karena banyak faktor yang mempengaruhi 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 ini terlepas dari desain perangkat keras yang mendasarinya. Namun, hal-hal lain - seperti lokalitas referensi (yaitu 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 baik, dan ini membuatnya lebih cepat daripada menggabungkan sortir dalam banyak kasus.

Selain itu, sangat mudah untuk menghindari run-time terburuk cases quicksort dari O ( n ² ) hampir seluruhnya dengan menggunakan pilihan yang tepat dari pivot - seperti mengambilnya secara acak (ini adalah strategi yang sangat baik).

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

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

Dalam RAM anggapan 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, maka quicksort terbunuh oleh fakta bahwa rata-rata disk 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 yang dilakukan mergesort.

Karena itu jika data harus diurutkan pada disk, Anda benar-benar ingin menggunakan beberapa variasi pada mergesort. (Umumnya Anda quicksort sublists, kemudian 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.

Sebenarnya, QuickSort adalah O (n ² ). Waktu berjalan rata - rata kasus adalah O (nlog (n)), tetapi kasus terburuknya adalah O (n ² ), 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.

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

Salah satu alasan psikologis yang belum diberikan adalah bahwa Quicksort lebih pintar dinamai. 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".

Seperti orang lain catat, kasus terburuk Quicksort adalah O (n ^ 2), sementara 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 tidak membaca setengah dari dua algoritma lainnya. Pada CPU modern, kinerja sangat didominasi oleh waktu akses, jadi pada akhirnya Quicksort menjadi pilihan pertama yang bagus.

Saya ingin menambahkan bahwa dari ketiga algoritme 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 mengurutkan algoritma untuk tinjauan umum yang baik.

Dari entri Wikipedia di Quicksort :

Quicksort juga bersaing dengan mergesort, algoritma pengurutan rekursif 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 membutuhkan Θ (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.)

Mu! Quicksort tidak lebih baik, ia sangat cocok untuk berbagai jenis aplikasi, 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 ^ 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

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.

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.

Saya ingin menambahkan ke jawaban yang ada beberapa matematika tentang bagaimana QuickSort berkinerja ketika menyimpang dari kasus terbaik dan bagaimana kemungkinan itu, yang saya harap akan membantu orang memahami sedikit lebih baik mengapa kasus O (n ^ 2) tidak nyata perhatian pada 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 vanilla 2-partisi 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 dari semua nilai yang sama dalam waktu O (n). Jadi menggunakan implementasi seperti itu berarti bahwa input dengan sejumlah kecil kunci benar-benar 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).

Seberapa besar 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

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

Dalam penerapan 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 3 indeks yang dipilih secara acak, dll. Dengan pengacakan ini dalam campuran, kami memiliki 2 kasus:

• Kumpulan data kecil. Kasus terburuk cukup masuk akal tetapi O (n ^ 2) tidak serempak 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 sangat 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 pada 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 pengurutannya akan selesai, jadi kasus terburuk atau apa pun di sekitarnya membutuhkan keberuntungan yang sangat 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 eksekusi dari kasus ideal. Seberapa besar kemungkinan kita tidak akan mencapai 22 pivot 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 jenis barang berjalan 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 lagi, 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 dirancang dan eksekusi selesai dalam waktu O (n * logn).

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 standar 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 java, 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 dari Minggu 3, Kursus Algoritma Princeton di Coursera

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.

Jawabannya akan sedikit condong ke arah quicksort wrt untuk perubahan yang dibawa dengan DualPivotQuickSort untuk nilai primitif. Ini digunakan dalam JAVA 7 untuk mengurutkan dalam 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

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 level 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 pivot point, 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 titik 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 penggabungan-penggabungan, Anda selalu berurusan dengan penggabungan elemen-N, di setiap tingkat tumpukan rekursif. Dengan penyortiran cepat, jumlah elemen yang Anda hadapi berkurang ketika 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.

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

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 semacam 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.

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, itu membutuhkan ruang 2n memeroy. Dan MergeSort juga perlu melakukan banyak salinan array, yang kami tidak termasuk dalam analisis algoritma. Singkatnya, MergeSort benar-benar lebih cepat daripada quicksort dalam theroy, tetapi pada kenyataannya Anda perlu mempertimbangkan ruang memeory, biaya salinan array, merger lebih lambat daripada jenis cepat. Saya pernah membuat Percobaan di mana saya diberi 10.00000 digit di java oleh kelas acak,dan butuh 2610ms dengan mergesort, 1370ms dengan quicksort.

Penyortiran cepat adalah kasus terburuk O (n ^ 2), namun, kasus rata-rata 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 pada penyatuan penggabungan ketika datang ke faktor konstan.

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

Informasi 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 pivot yang buruk adalah 0,5 * n. Berdasarkan probabilitas ini quick sort efisien untuk kasus rata-rata (dan tipikal).

Ini adalah pertanyaan yang cukup lama, tetapi karena saya sudah membahas keduanya baru-baru ini adalah 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. Tidak banyak manfaat dari array yang sudah diurutkan dalam hal perbandingan (namun 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 quicksort mengungguli mergesort hingga 25%.

Namun jika array (besar) Anda memiliki nilai unik yang sangat sedikit, penggabungan sortir mulai mendapatkan lebih cepat.

Jadi mungkin intinya adalah: jika perbandingan itu mahal (mis. Fungsi callback, membandingkan string, membandingkan banyak bagian struktur yang sebagian besar mendapatkan "kedua" ketiga-keempat) - 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

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.

Ini adalah pertanyaan umum yang diajukan dalam wawancara bahwa meskipun kinerja kasus penggabungan terburuk yang lebih baik, quicksort dianggap lebih baik daripada penggabungan, terutama untuk input besar. Ada beberapa alasan tertentu karena quicksort mana yang lebih baik:

1- Ruang Bantu: Pengurutan cepat adalah algoritma pengurutan di tempat. Penyortiran di tempat berarti tidak diperlukan ruang penyimpanan tambahan untuk melakukan penyortiran. Penggabungan sortir di sisi lain memerlukan array sementara untuk menggabungkan array yang diurutkan dan karenanya tidak ada di tempat.

2- Kasus terburuk: Kasus terburuk quicksort O(n^2)dapat dihindari dengan menggunakan quicksort acak. Ini dapat dengan mudah dihindari dengan probabilitas tinggi dengan memilih pivot yang tepat. Memperoleh perilaku kasus rata-rata dengan memilih elemen pivot yang tepat membuatnya berimprovisasi pada kinerja dan menjadi seefisien penggabungan.

3 - Lokalitas referensi: Quicksort khususnya menunjukkan lokalitas cache yang baik dan ini membuatnya lebih cepat daripada menggabungkan semacam dalam banyak kasus seperti di lingkungan memori virtual.

4- Ekor rekursi: QuickSort adalah ekor rekursif sedangkan jenis Penggabungan tidak. Fungsi ekor rekursif adalah fungsi di mana panggilan rekursif adalah hal terakhir yang dilakukan oleh fungsi. Fungsi rekursif ekor dianggap lebih baik daripada fungsi rekursif non-ekor karena rekursi ekor dapat dioptimalkan oleh kompiler.

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 bisa 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 terdegradasi 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 bisa berasal dari sumber jahat, Anda tidak boleh menggunakan quicksort biasa.

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 melihat radix atau bucket type. 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 punya bukti bahwa Anda tidak dapat membandingkan sortir 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-integer: http://www.stereopsis.com/radix.html . Perhatikan bahwa trik membalik bit dapat digunakan terlepas dari algoritma pengurutan apa yang sebenarnya Anda gunakan ...

Tambahan kecil untuk quick vs merge sort.

Juga dapat bergantung 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)

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 bisa menyisipkan item di tengah dengan O (1) ruang dan O (1) waktu, oleh karena itu operasi penggabungan dalam semacam gabungan dapat diimplementasikan tanpa ruang tambahan. 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 memerlukan banyak akses memori acak dan dengan 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 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).

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.

Di tanah c / c ++, ketika tidak menggunakan wadah stl, saya cenderung menggunakan quicksort, karena itu dibangun ke dalam run time, sedangkan mergesort tidak.

Jadi saya percaya bahwa dalam banyak kasus, itu hanyalah jalan perlawanan paling sedikit.

Selain itu kinerja bisa jauh lebih tinggi dengan pengurutan cepat, untuk kasus di mana seluruh dataset tidak masuk ke dalam set kerja.

Salah satu alasannya lebih filosofis. Quicksort adalah filosofi Top-> Down. Dengan n elemen untuk disortir, ada n! kemungkinan. Dengan 2 partisi m & nm yang saling eksklusif, jumlah kemungkinan turun dalam beberapa urutan besarnya. m! * (nm)! lebih kecil dengan beberapa pesanan daripada n! sendirian. bayangkan 5! vs 3! * 2 !. 5! memiliki kemungkinan 10 kali lebih banyak daripada 2 partisi masing-masing 2 & 3. dan memperkirakan 1 juta faktorial vs 900 ribu! * 100 ribu! vs. Jadi, alih-alih khawatir tentang membuat urutan apa pun dalam kisaran atau partisi, hanya membuat pesanan di tingkat yang lebih luas di partisi dan mengurangi kemungkinan di dalam partisi. Setiap pesanan yang dibuat sebelumnya dalam suatu rentang akan terganggu kemudian jika partisi itu sendiri tidak saling eksklusif.

Setiap pendekatan pesanan dari bawah ke atas seperti semacam gabungan atau semacam tumpukan adalah seperti pendekatan pekerja atau karyawan di mana orang mulai membandingkan pada tingkat mikroskopis awal. Tetapi urutan ini pasti akan hilang segera setelah elemen di antara mereka ditemukan kemudian. Pendekatan ini sangat stabil & sangat dapat diprediksi tetapi melakukan sejumlah pekerjaan tambahan.

Penyortiran Cepat adalah seperti pendekatan Manajerial di mana seseorang pada awalnya tidak peduli tentang pesanan apa pun, hanya tentang memenuhi kriteria luas dengan Tidak memperhatikan pesanan. Kemudian partisi dipersempit sampai Anda mendapatkan set yang diurutkan. Tantangan nyata di Quicksort adalah menemukan partisi atau kriteria dalam kegelapan ketika Anda tidak tahu apa-apa tentang elemen yang akan diurutkan. Itulah mengapa kita perlu melakukan upaya untuk menemukan nilai median atau memilih 1 secara acak atau pendekatan "Manajerial" yang sewenang-wenang. Untuk menemukan median yang sempurna dapat mengambil banyak upaya dan mengarah ke pendekatan bottom up yang bodoh lagi. Jadi Quicksort mengatakan hanya dengan memilih pivot acak dan berharap itu akan berada di suatu tempat di tengah atau melakukan pekerjaan untuk menemukan median 3, 5 atau sesuatu yang lebih untuk menemukan median yang lebih baik tetapi tidak berencana untuk menjadi sempurna & jangan ' Jangan buang waktu pada awalnya memesan. Itu tampaknya baik jika Anda beruntung atau kadang-kadang menurunkan ke n ^ 2 ketika Anda tidak mendapatkan median tetapi hanya mengambil kesempatan. Bagaimanapun data bersifat acak. Baik. Jadi saya lebih setuju dengan top -> pendekatan logis quicksort & ternyata kesempatan yang dibutuhkan tentang pemilihan pivot & perbandingan yang dihemat sebelumnya tampaknya bekerja lebih baik lebih sering daripada pendekatan bottom-up yang teliti & teliti stabil>> seperti menggabungkan semacam. Tapi perbandingan yang dihemat sebelumnya tampaknya bekerja lebih baik lebih sering daripada pendekatan bottom -> stabil yang teliti & teliti seperti penggabungan. Tapi perbandingan yang dihemat sebelumnya tampaknya bekerja lebih baik lebih sering daripada pendekatan bottom -> stabil yang teliti & teliti seperti penggabungan. Tapi