Mengapa quicksort lebih baik daripada algoritma pengurutan lainnya dalam praktik?

31

Ini adalah pos ulang pertanyaan di cs.SE oleh Janoma . Kredit penuh dan rampasan untuknya atau cs.SE.

Dalam kursus algoritma standar kita diajarkan bahwa quicksort rata-rata adalah O (n log n) dan O (n²) dalam kasus terburuk. Pada saat yang sama, algoritma pengurutan lainnya dipelajari yaitu O (n log n) dalam kasus terburuk (seperti mergesort dan heapsort ), dan bahkan waktu linear dalam kasus terbaik (seperti bubblesort ) tetapi dengan beberapa kebutuhan memori tambahan.

Setelah sekilas melihat beberapa waktu berlari , wajar untuk mengatakan bahwa quicksort tidak seefisien yang lainnya.

Juga, pertimbangkan bahwa siswa belajar dalam kursus pemrograman dasar bahwa rekursi tidak benar-benar baik secara umum karena dapat menggunakan terlalu banyak memori, dll. Oleh karena itu (dan meskipun ini bukan argumen nyata), ini memberikan gagasan bahwa quicksort mungkin tidak sangat bagus karena merupakan algoritma rekursif.

Mengapa, kemudian, apakah quicksort mengungguli algoritma pengurutan lainnya dalam praktek? Apakah itu ada hubungannya dengan struktur data dunia nyata ? Apakah itu ada hubungannya dengan cara memori bekerja di komputer? Saya tahu bahwa beberapa ingatan jauh lebih cepat daripada yang lain, tetapi saya tidak tahu apakah itu alasan sebenarnya untuk kinerja kontra-intuitif ini (bila dibandingkan dengan perkiraan teoritis).

Raphael
sumber
3
Reputasi Quicksort berasal dari masa ketika cache tidak ada.
Pemrogram
9
"Mengapa quicksort mengungguli algoritma pengurutan lainnya dalam praktek?" Yakin itu benar? Tunjukkan pada kami implementasi nyata yang Anda referensikan dengan pernyataan ini, dan komunitas akan memberi tahu Anda mengapa implementasi spesifik berperilaku seperti itu. Segala sesuatu yang lain akan mengarah pada tebakan liar tentang program yang tidak ada.
Doc Brown
1
@DocBrown: Banyak implementasi Quicksort (atau varian) dipilih di banyak perpustakaan, bisa dibilang karena mereka berkinerja terbaik (saya harap begitu, itu). Jadi mungkin ada sesuatu tentang algoritma yang membuat Quicksort cepat, terlepas dari implementasinya .
Raphael
1
Seseorang harus mengatakan ini untuk kelengkapan, jadi saya akan: Quicksort tidak (biasanya) stabil. Karena alasan ini, Anda mungkin tidak ingin menggunakannya. Juga, untuk alasan ini, pengurutan default Anda mungkin bukan Quicksort bahkan ketika itu yang Anda inginkan.
RalphChapin
1
@Raphael: Seringkali yang disebut quick sort sebenarnya adalah beberapa variasi seperti intro sort (digunakan, afaik, di pustaka standar C ++), bukan quick quick murni.
Giorgio

Jawaban:

21

Saya tidak akan setuju bahwa quicksort lebih baik daripada algoritma pengurutan lainnya dalam praktiknya.

Untuk sebagian besar tujuan, Timsort - hibrid antara jenis mergesort / penyisipan yang mengeksploitasi fakta bahwa data yang Anda urutkan sering dimulai hampir diurutkan atau diurutkan mundur.

Quicksort yang paling sederhana (tanpa pivot acak) memperlakukan kasus yang berpotensi umum ini sebagai O (N ^ 2) (dikurangi menjadi O (N lg N) dengan pivot acak), sementara TimSort dapat menangani kasus ini dalam O (N).

Menurut tolok ukur ini dalam C # yang membandingkan quicksort bawaan dengan TimSort, Timsort secara signifikan lebih cepat dalam sebagian besar kasus yang diurutkan, dan sedikit lebih cepat dalam kasus data acak dan TimSort menjadi lebih baik jika fungsi perbandingan sangat lambat. Saya belum mengulangi tolok ukur ini dan tidak akan terkejut jika quicksort sedikit mengalahkan TimSort untuk beberapa kombinasi data acak atau jika ada sesuatu yang unik dalam jenis builtin C # (berdasarkan quicksort) yang memperlambatnya. Namun, TimSort memiliki keuntungan yang berbeda ketika data dapat diurutkan sebagian, dan kira-kira sama dengan quicksort dalam hal kecepatan ketika data tidak diurutkan sebagian.

TimSort juga memiliki bonus tambahan untuk menjadi yang stabil, tidak seperti quicksort. Satu-satunya kelemahan TimSort menggunakan memori O (N) versus O (lg N) dalam implementasi (cepat) yang biasa.

dr jimbob
sumber
18

Sortir cepat dianggap lebih cepat karena koefisiennya lebih kecil daripada algoritma lainnya yang diketahui. Tidak ada alasan atau bukti untuk itu, hanya tidak ada algoritma dengan koefisien yang lebih kecil telah ditemukan. Memang benar bahwa algoritma lain juga memiliki waktu O ( n log n ), tetapi di dunia nyata koefisien juga penting.

Perhatikan bahwa untuk jenis penyisipan data kecil (yang dianggap O ( n 2 )) lebih cepat karena sifat fungsi matematika. Ini tergantung pada koefisien spesifik yang bervariasi dari mesin ke mesin. (Pada akhirnya, hanya perakitan yang benar-benar berjalan.) Jadi kadang-kadang hibrida jenis cepat dan jenis penyisipan adalah yang tercepat dalam praktiknya saya pikir.

Ramzi Kahil
sumber
7
+ Benar. Para guru perlu lebih sadar (dan saya adalah seorang guru) tentang fakta bahwa faktor-faktor konstan dapat bervariasi berdasarkan urutan besarnya. Jadi keterampilan tuning kinerja sangat penting, terlepas dari O-besar. Masalahnya adalah, mereka terus mengajar gprof , hanya karena mereka harus melewati poin itu dalam kurikulum, yang merupakan pendekatan yang salah 180 derajat.
Mike Dunlavey
2
"Tidak ada alasan atau keuntungan untuk itu": pasti ada. Jika Anda menggali cukup dalam, Anda akan menemukan alasannya.
Gilles 'SANGAT berhenti menjadi jahat'
2
@ B Tujuh: untuk menyederhanakan banyak ... untuk algoritma pengurutan O (n log n), ada (n log n) iterasi dari pengurutan loop untuk mengurutkan n item. Koefisiennya adalah berapa lama setiap siklus loop berlangsung. Ketika n benar-benar besar (setidaknya ribuan), koefisien tidak masalah sebanyak O () bahkan jika koefisiennya besar. Tetapi ketika n kecil, koefisien penting - dan bisa menjadi hal paling penting jika Anda hanya menyortir 10 item.
Matt Gallagher
4
@ MikeDunlavey - contoh yang baik adalah bahwa membangun piramida adalah O (n) saat menyortir foto Anda adalah O (n ln n) tetapi yang lebih cepat!
Martin Beckett
2
Ada dijamin O (n log n) algoritma seperti heapsort dan mergesort, jadi dalam istilah terburuk asimtotik Quicksort bahkan tidak sama cepatnya dengan yang terbaik. Tetapi dalam kinerja dunia nyata, beberapa varian quicksort bekerja sangat baik. Namun mengatakan "koefisiennya lebih kecil" seperti mengatakan "lebih cepat karena lebih cepat". Mengapa faktor konstan begitu kecil? Alasan utamanya adalah karena quicksort sangat bagus dalam hal lokalitas - ini membuat penggunaan cache sangat baik. Mergesort juga memiliki lokasi yang baik, tetapi sangat sulit dilakukan di tempat.
Steve314
16

Quicksort tidak mengungguli semua algoritma penyortiran lainnya. Misalnya, bottom-up heap sort ( Wegener 2002 ) mengungguli quicksort untuk jumlah data yang masuk akal dan juga merupakan algoritma di tempat. Ini juga mudah diimplementasikan (setidaknya, tidak lebih keras dari beberapa varian quicksort yang dioptimalkan).

Itu tidak begitu terkenal dan Anda tidak menemukannya di banyak buku pelajaran, yang mungkin menjelaskan mengapa itu tidak sepopuler quicksort.

Doc Brown
sumber
+1: Saya telah menjalankan beberapa tes dan memang menggabungkan semacam itu pasti lebih baik daripada menyortir cepat untuk array besar (> 100000 elemen). Heap sort sedikit lebih buruk daripada merge sort (tapi merge sort membutuhkan lebih banyak memori). Saya pikir apa yang orang sebut semacam cepat sering variasi yang disebut jenis intro: jenis cepat yang jatuh kembali ke tumpukan tumpukan ketika kedalaman rekursi melampaui batas tertentu.
Giorgio
@Giorgio: quicksort dapat dimodifikasi dengan beberapa cara untuk memperbaikinya, lihat misalnya di sini: algs4.cs.princeton.edu/23quicksort Apakah Anda mencoba peningkatan itu?
Doc Brown
Menarik, dapatkah Anda meninggalkan referensi ke buku \ situs untuk membaca lebih lanjut tentang itu? (lebih disukai sebuah buku)
Ramzi Kahil
@ Martin: maksud Anda tentang bottom-up heapsort? Baiklah, saya memberi referensi di atas. Jika Anda menginginkan sumber daya gratis, wikipedia Jerman memiliki artikel tentang itu ( de.wikipedia.org/wiki/BottomUp-Heapsort ). Bahkan jika Anda tidak berbicara bahasa Jerman, saya rasa Anda masih bisa membaca contoh C99.
Doc Brown
7

Anda seharusnya tidak hanya berpusat pada kasus terburuk dan hanya pada kompleksitas waktu. Ini lebih tentang rata-rata daripada yang terburuk, dan ini tentang waktu dan ruang.

Quicksort:

  • memiliki kompleksitas waktu rata - rata Θ ( n log n );
  • dapat diimplementasikan dengan kompleksitas ruang Θ (log n );

Juga memiliki catatan bahwa notasi O besar tidak memperhitungkan konstanta, tetapi dalam praktiknya itu membuat perbedaan jika algoritma beberapa kali lebih cepat. Θ ( n log n ) berarti, algoritma yang dijalankan dalam K  n  log ( n ), di mana K adalah konstan. Quicksort adalah algoritma perbandingan-jenis dengan K terendah .

vartec
sumber
1
@Gilles: memiliki K rendah, karena ini adalah algoritma yang sederhana.
vartec
5
WTF? Ini tidak masuk akal. Kesederhanaan suatu algoritma tidak memiliki hubungan dengan kecepatannya. Sortir pilihan lebih sederhana daripada quicksort, itu tidak membuatnya lebih cepat.
Gilles 'SANGAT berhenti menjadi jahat'
1
@Gilles: jenis seleksi adalah O (n ^ 2) untuk kasus apa pun (terburuk, rata-rata, dan terbaik). Jadi tidak masalah seberapa sederhana itu. Quicksort adalah O (n log n) untuk kasus rata-rata, dan di antara semua algos dengan O (n log n) rata-rata adalah yang paling sederhana.
vartec
1
@Gilles: hal-hal lain dianggap sama, kesederhanaan membantu kinerja. Katakanlah Anda membandingkan dua algoritma yang masing-masing mengambil (K n log n) iterasi dari masing-masing loop dalam: algoritma yang perlu melakukan lebih sedikit barang per loop memiliki keunggulan kinerja.
badai
1
@comingstorm: Frasa seperti pernyataan Anda adalah tautologi, tetapi tidak terkait dengan "kesederhanaan". Sebagai contoh, ada varian Quicksort yang lebih rumit (perbedaan kasus!) Yang menghasilkan runtime yang lebih kecil (baik secara teori maupun praktik).
Raphael
5

Quicksort seringkali merupakan pilihan yang baik karena cukup cepat dan cukup cepat serta mudah diimplementasikan.

Jika Anda serius menyortir data dalam jumlah besar dengan sangat cepat maka Anda mungkin lebih baik dengan beberapa variasi pada MergeSort. Ini dapat dibuat untuk mengambil keuntungan dari penyimpanan eksternal, dapat menggunakan beberapa utas atau bahkan proses tetapi tidak sepele terhadap kode.

James Anderson
sumber
1

Kinerja algoritma yang sebenarnya tergantung pada platform, serta bahasa, kompiler, perhatian programmer terhadap detail implementasi, upaya pengoptimalan spesifik, dan lain-lain. Jadi, "keunggulan faktor konstan" quicksort tidak terlalu terdefinisi dengan baik - ini adalah penilaian subjektif berdasarkan alat yang tersedia saat ini, dan perkiraan kasar "upaya implementasi yang setara" oleh siapa pun yang benar-benar melakukan studi kinerja komparatif .. .

Yang mengatakan, saya percaya quicksort berkinerja baik (untuk input acak) karena sederhana, dan karena struktur rekursifnya relatif ramah terhadap cache. Di sisi lain, karena kasus terburuknya mudah dipicu, setiap penggunaan praktis quicksort harus lebih kompleks daripada deskripsi buku teksnya akan menunjukkan: dengan demikian, versi yang dimodifikasi seperti introsort.

Seiring berjalannya waktu, ketika platform dominan berubah, algoritme yang berbeda dapat memperoleh atau kehilangan keunggulan relatifnya (tidak jelas). Kearifan konvensional tentang kinerja relatif mungkin tertinggal dari perubahan ini, jadi jika Anda benar-benar tidak yakin algoritma mana yang terbaik untuk aplikasi Anda, Anda harus mengimplementasikan keduanya, dan mengujinya.

datang badai
sumber
Saya kira "konstanta yang lebih kecil" yang dihubungkan dengan itu adalah yang ada dalam analisis formal, yaitu tentang jumlah perbandingan atau pertukaran. Ini didefinisikan dengan sangat baik tetapi tidak jelas bagaimana ini diterjemahkan menjadi runtime. Seorang kolega saat ini melakukan penelitian tentang itu, sebenarnya.
Raphael
Kesan saya adalah itu tentang kinerja umum, tetapi saya tidak akan mengandalkan keduanya. Kau benar, meskipun: jika dibandingkan Anda sangat mahal, Anda dapat melihat jumlah perbandingan diharapkan ...
comingstorm
1
Karena alasan yang Anda nyatakan, berbicara tentang kinerja keseluruhan (berdasarkan waktu) tidak berarti dalam kasus umum karena terlalu banyak faktor detail. Alasan untuk menghitung hanya operasi tertentu bukan karena harganya mahal, tetapi karena terjadi "paling sering "Dalam pengertian Landau-notation (Big-Oh), jadi menghitung itu memberi Anda asimptotik kasar Anda. Segera setelah Anda mempertimbangkan konstanta dan / atau runtime, strategi ini jauh lebih menarik.
Raphael
Implementasi QuickSort yang baik akan dikompilasi sedemikian sehingga nilai pivot Anda tetap berada dalam register CPU selama diperlukan. Ini sering cukup untuk mengalahkan jenis yang secara teoritis lebih cepat dengan waktu Big-O yang sebanding.
Dan Lyons
Algoritme sort yang berbeda memiliki karakteristik yang berbeda sehubungan dengan jumlah perbandingan dan jumlah simpang susun yang mereka lakukan. Dan @DanLyons mencatat bahwa pengurutan tipikal dalam pustaka melakukan perbandingannya melalui fungsi yang disediakan pengguna, dan menjaga nilai dalam register di banyak panggilan fungsi cukup rumit.
Runcing