Kapan setiap algoritma pengurutan digunakan? [Tutup]

Apa kasus penggunaan ketika algoritma pengurutan tertentu lebih disukai daripada yang lain - menggabungkan sort vs QuickSort vs heapsort vs 'intro sort', dll?

Apakah ada panduan yang disarankan dalam menggunakannya berdasarkan ukuran, jenis struktur data, memori dan cache yang tersedia, dan kinerja CPU?

Pertama, definisi, karena ini cukup penting: Jenis yang stabil adalah yang dijamin tidak akan menyusun ulang elemen dengan kunci yang identik.

Rekomendasi:

Sortir cepat: Ketika Anda tidak memerlukan sortasi yang stabil dan kinerja case rata-rata lebih penting daripada kinerja case terburuk. Jenis cepat adalah O (N log N) rata-rata, O (N ^ 2) dalam kasus terburuk. Implementasi yang baik menggunakan penyimpanan tambahan O (log N) dalam bentuk ruang stack untuk rekursi.

Urutkan gabungan: Ketika Anda membutuhkan jenis, stabil O (N log N), ini adalah satu-satunya pilihan Anda. Satu-satunya kelemahan untuk itu adalah bahwa ia menggunakan ruang bantu O (N) dan memiliki konstanta sedikit lebih besar daripada jenis cepat. Ada beberapa jenis penggabungan di tempat, tetapi AFAIK semuanya tidak stabil atau lebih buruk daripada O (N log N). Bahkan O (N log N) pada jenis tempat memiliki konstanta yang jauh lebih besar daripada jenis gabungan lama biasa sehingga mereka lebih keingintahuan teoretis daripada algoritma yang berguna.

Heap sort: Ketika Anda tidak membutuhkan sortir yang stabil dan Anda lebih peduli dengan kinerja case terburuk daripada performa case rata-rata. Ini dijamin menjadi O (N log N), dan menggunakan O (1) ruang tambahan, yang berarti bahwa Anda tidak akan kehabisan tumpukan atau menumpuk ruang pada input yang sangat besar.

Introsort: Ini adalah jenis cepat yang beralih ke jenis tumpukan setelah kedalaman rekursi tertentu untuk mengatasi kasus terburuk O (N ^ 2) jenis cepat. Ini hampir selalu lebih baik daripada jenis cepat lama, karena Anda mendapatkan kasus rata-rata jenis cepat, dengan jaminan kinerja O (N log N). Mungkin satu-satunya alasan untuk menggunakan heap sort bukan ini adalah pada sistem dengan keterbatasan memori di mana ruang stack O (log N) praktis signifikan.

Jenis penyisipan : Ketika N dijamin kecil, termasuk sebagai dasar kasus penyortiran cepat atau gabungan. Meskipun ini O (N ^ 2), ia memiliki konstanta yang sangat kecil dan merupakan jenis yang stabil.

Bubble sort, sort sort : Ketika Anda melakukan sesuatu yang cepat dan kotor dan karena alasan tertentu Anda tidak bisa hanya menggunakan algoritma pengurutan perpustakaan standar. Satu-satunya keuntungan yang dimiliki jenis penyisipan ini adalah sedikit lebih mudah diterapkan.

Jenis non-perbandingan: Dalam beberapa kondisi yang cukup terbatas dimungkinkan untuk memecahkan penghalang O (N log N) dan mengurutkan dalam O (N). Berikut adalah beberapa kasus yang patut dicoba:

Counting sort: Ketika Anda menyortir bilangan bulat dengan rentang terbatas.

Urutan Radix: Ketika log (N) secara signifikan lebih besar dari K, di mana K adalah jumlah digit radix.

Sortir bucket: Bila Anda dapat menjamin bahwa input Anda didistribusikan secara merata.

Quicksort biasanya yang tercepat rata-rata, tetapi memiliki beberapa perilaku terburuk yang cukup buruk. Jadi, jika Anda harus menjamin tidak ada data buruk yang memberi Anda O(N^2), Anda harus menghindarinya.

Gabung-sort menggunakan memori tambahan, tetapi sangat cocok untuk penyortiran eksternal (yaitu file besar yang tidak sesuai dengan memori).

Heap-sort dapat mengurutkan di tempat dan tidak memiliki perilaku kuadratik kasus terburuk, tetapi rata-rata lebih lambat daripada quicksort dalam kebanyakan kasus.

Di mana hanya bilangan bulat dalam rentang terbatas yang terlibat, Anda dapat menggunakan semacam radix untuk membuatnya sangat cepat.

Dalam 99% kasus, Anda akan baik-baik saja dengan jenis perpustakaan, yang biasanya didasarkan pada quicksort.

Halaman Wikipedia tentang algoritma pengurutan memiliki grafik perbandingan yang bagus.

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Apa yang tidak dipertimbangkan oleh tautan yang disediakan untuk perbandingan / animasi adalah ketika jumlah data melebihi memori yang tersedia --- pada saat itu jumlah lintasan data, yaitu biaya I / O, mendominasi runtime. Jika Anda perlu melakukan itu, baca "sorting eksternal" yang biasanya mencakup varian jenis gabungan dan tumpukan.

http://corte.si/posts/code/visualisingsorting/index.html dan http://corte.si/posts/code/timsort/index.html juga memiliki beberapa gambar keren yang membandingkan berbagai algoritma penyortiran.

@dsimcha menulis: Menghitung urut: Saat Anda menyortir bilangan bulat dengan rentang terbatas

Saya akan mengubahnya menjadi:

Counting sort: Ketika Anda mengurutkan bilangan bulat positif (0 - Integer.MAX_VALUE-2 karena lubang pigeon).

Anda selalu bisa mendapatkan nilai maksimum dan minimum sebagai heuristik efisiensi dalam waktu linier juga.
Anda juga memerlukan setidaknya n ruang ekstra untuk array perantara dan itu jelas stabil.

/**
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

(meskipun sebenarnya akan memungkinkan untuk MAX_VALUE-2) lihat: Apakah array Java memiliki ukuran maksimum?

Saya juga akan menjelaskan bahwa kompleksitas jenis radix adalah O (wn) untuk kunci n yang merupakan bilangan bulat dari ukuran kata w. Terkadang w ditampilkan sebagai konstanta, yang akan membuat radix sort lebih baik (untuk n yang cukup besar) daripada algoritma sorting berbasis perbandingan terbaik, yang semuanya melakukan perbandingan O (n log n) untuk mengurutkan n key. Namun, secara umum, w tidak dapat dianggap sebagai konstanta: jika semua n kunci berbeda, maka w harus setidaknya log n untuk mesin akses-acak untuk dapat menyimpannya dalam memori, yang memberikan kompleksitas waktu terbaik. (n log n). (dari wikipedia)