Mengapa Collections.sort menggunakan merge sort daripada quicksort?

101

Kami tahu bahwa pengurutan cepat adalah algoritme pengurutan tercepat.

JDK6 collections.sortmenggunakan algoritme pengurutan gabungan, bukan pengurutan cepat. Tapi Arrays.sort menggunakan algoritma pengurutan cepat.

Apa alasan Collections.sort menggunakan jenis gabungan, bukan pengurutan cepat?

java sorting collections MayurB
sumber
3
Kecuali Anda bisa meminta penulis JDK untuk menjawab, yang akan Anda dapatkan hanyalah menebak. Bukan pertanyaan nyata.
Marquis dari Lorne
4
@EJP Poin yang bagus, tapi tentunya "Tidak konstruktif" adalah alasan penutupan yang tepat. Jelas bagi saya apa pertanyaannya di sini.
Duncan Jones
2
Karena orang-orang Java memutuskan untuk melakukannya seperti ini. Tanya mereka. Saya pikir Anda tidak bisa mendapatkan jawaban yang sah di sini. Dan penyortiran cepat bukanlah yang terbaik. Ini hanya yang terbaik untuk penggunaan umum .
Adam Arold
4
Satu tebakan: Quicksort tidak stabil, Mergesort adalah. Untuk primitif, pengurutan stabil / non-stabil tidak relevan, untuk objek mungkin (atau setidaknya, Anda mungkin mendapatkan bug yang diajukan terhadap pengurutan yang tidak stabil).
parsifal
2
@EJP, Tidak ada yang menghentikan niat penulis JDK untuk dipublikasikan. Setelah publik, kita tidak perlu penulis sendiri menjawab. Sebenarnya mungkin untuk mendapatkan jawaban yang lebih dari sekadar menebak bahkan tanpa jawaban dari penulis JDK.
Pacerier

Jawaban:

187

Sangat mungkin dari Josh Bloch § :

Saya memang menulis metode ini, jadi saya kira saya memenuhi syarat untuk menjawab. Memang benar bahwa tidak ada satu pun algoritma pengurutan terbaik. QuickSort memiliki dua kekurangan utama jika dibandingkan dengan mergesort:

  1. Itu tidak stabil (seperti yang dicatat parsifal).

  2. Itu tidak menjamin kinerja n log n; itu dapat menurunkan kinerja kuadrat pada input patologis.

Stabilitas bukanlah masalah untuk tipe primitif, karena tidak ada gagasan tentang identitas yang berbeda dari persamaan (nilai). Dan kemungkinan perilaku kuadrat dianggap tidak menjadi masalah dalam praktik untuk implementasi Bentely dan McIlroy (atau selanjutnya untuk Dual Pivot Quicksort ), itulah mengapa varian QuickSort ini digunakan untuk jenis primitif.

Stabilitas adalah masalah besar saat menyortir objek arbitrer. Misalnya, Anda memiliki objek yang mewakili pesan email, dan Anda mengurutkannya terlebih dahulu menurut tanggal, lalu menurut pengirim. Anda mengharapkan mereka diurutkan berdasarkan tanggal dalam setiap pengirim, tetapi itu hanya akan benar jika pengurutannya stabil. Itulah mengapa kami memilih untuk menyediakan sortir stabil (Merge Sort) untuk mengurutkan referensi objek. (Secara teknis, beberapa pengurutan stabil berurutan menghasilkan pengurutan leksikografik pada kunci dalam urutan kebalikan dari pengurutan: pengurutan terakhir menentukan subkunci yang paling signifikan.)

Ini adalah keuntungan sampingan yang bagus bahwa Merge Sort menjamin kinerja n log n (waktu) apapun inputnya. Tentu saja ada sisi negatifnya: pengurutan cepat adalah pengurutan "di tempat": ia hanya memerlukan log n ruang eksternal (untuk mempertahankan tumpukan panggilan). Merge, sort, di sisi lain, membutuhkan O (n) ruang eksternal. Varian TimSort (diperkenalkan di Java SE 6) membutuhkan lebih sedikit ruang (O (k)) jika larik input hampir diurutkan.

Juga, berikut ini relevan:

Algoritme yang digunakan oleh java.util.Arrays.sort dan (secara tidak langsung) oleh java.util.Collections.sort untuk mengurutkan referensi objek adalah "gabungan yang dimodifikasi (di mana penggabungan dihilangkan jika elemen tertinggi di sublist rendah kurang dari elemen terendah di sublist tinggi). " Ini adalah jenis stabil yang cukup cepat yang menjamin kinerja O (n log n) dan membutuhkan O (n) ruang ekstra. Pada zamannya (ditulis pada tahun 1997 oleh Joshua Bloch), itu adalah pilihan yang bagus, tetapi hari ini tetapi kami dapat melakukan yang lebih baik.

Sejak 2003, list sort Python telah menggunakan algoritme yang dikenal sebagai timsort (setelah Tim Peters, yang menulisnya). Ini adalah penggabungan yang stabil, adaptif, dan berulang yang membutuhkan jauh lebih sedikit dari n log (n) perbandingan saat berjalan pada larik yang diurutkan sebagian, sambil menawarkan kinerja yang sebanding dengan penggabungan tradisional saat dijalankan pada larik acak. Seperti semua penggabungan yang tepat, timsort stabil dan berjalan dalam waktu O (n log n) (kasus terburuk). Dalam kasus terburuk, timsort membutuhkan ruang penyimpanan sementara untuk n / 2 referensi objek; dalam kasus terbaik, ini hanya membutuhkan sedikit ruang konstan. Bandingkan ini dengan implementasi saat ini, yang selalu membutuhkan ruang ekstra untuk n referensi objek, dan mengalahkan n log n hanya pada daftar yang hampir diurutkan.

Timsort dijelaskan secara rinci di sini: http://svn.python.org/projects/python/trunk/Objects/listsort.txt .

Implementasi asli Tim Peters ditulis dalam C. Joshua Bloch memindahkannya dari C ke Java dan mengakhiri pengujian, benchmark, dan tuning kode yang dihasilkan secara ekstensif. Kode yang dihasilkan adalah pengganti drop-in untuk java.util.Arrays.sort. Pada data yang sangat teratur, kode ini dapat berjalan hingga 25 kali lebih cepat dari implementasi saat ini (pada VM server HotSpot). Pada data acak, kecepatan implementasi lama dan baru sebanding. Untuk daftar yang sangat pendek, implementasi baru secara substansial lebih cepat daripada yang lama bahkan pada data acak (karena menghindari penyalinan data yang tidak perlu).

Juga, lihat Apakah Java 7 menggunakan Tim Sort untuk Method Arrays.Sort?.

Tidak ada satu pun pilihan "terbaik". Seperti banyak hal lainnya, ini tentang pengorbanan.

NPE
sumber