Hanya ingin tahu mengapa Javadan .NET Frameworkmenggunakan algoritma pengurutan yang berbeda secara default.
Di Jawa, Array.Sort() gunakan algoritma Merge Sort secara default dan seperti yang dikatakan Wikipedia.com :
Di Jawa, metode Arrays.sort () menggunakan pengurutan gabungan atau quicksort yang disetel tergantung pada tipe data dan untuk efisiensi implementasi, beralih ke pengurutan penyisipan ketika kurang dari tujuh elemen array sedang diurutkan.
Dalam .NET Framework Array.Sort/List.Sort() menggunakan Quick Sort sebagai algoritma penyortiran default ( MSDN ):
List.Sort () menggunakan Array.Sort, yang menggunakan algoritma QuickSort. Implementasi ini melakukan jenis yang tidak stabil; yaitu, jika dua elemen sama, urutannya mungkin tidak dipertahankan. Sebaliknya, jenis stabil menjaga urutan elemen yang sama.
Dengan melihat tabel "Perbandingan algoritma" yang hebat, kita dapat melihat bahwa kedua algoritma memiliki perilaku yang sangat berbeda dari perspektif Penggunaan Kasus dan Memori Terburuk:
Keduanya Javadan .NETmerupakan Kerangka yang bagus untuk pengembangan Solusi Perusahaan, keduanya memiliki platform untuk pengembangan yang disematkan. Jadi mengapa mereka menggunakan algoritma penyortiran yang berbeda secara default, ada pemikiran?
Jawaban:
Seperti deterministik seperti komputer itu sendiri, teknik komputer bukanlah ilmu pasti. Dua orang, diberi domain masalah yang sama, akan melakukan analisis dan mengembangkan dua solusi berbeda yang memenuhi semua kendala masalah. Mungkin sulit atau tidak mungkin untuk menentukan secara empiris mana dari yang ini "lebih baik" dalam kasus umum.
Dugaan saya adalah .NET QuickSort berlapis di atas sesuatu di MFC atau Windows API, dan mungkin diwarisi dari versi Windows yang jauh lebih lama di mana keuntungan multi-threadable MergeSort bahkan tidak akan dipertimbangkan untuk komputer hari itu ( EDIT: tidak, meskipun pengembang Microsoft telah menjadi fanboy QuickSort untuk waktu yang lama, sebagaimana dibuktikan oleh pilihan implementasi penyortiran ini sejak MS-DOS).
Java, yang tidak dapat menggunakan implementasi platform khusus karena Java dirancang dari awal untuk sepenuhnya platform-independen, berjalan dengan cara yang berbeda. Siapa yang tahu mengapa MergeSort keluar di atas; Dugaan saya yang liar adalah bahwa implementasinya memenangkan semacam kompetisi kinerja versus beberapa jenis lainnya yang dikembangkan oleh pengembang, atau selain itu ruang O (n) -gegegege hanya terlihat terbaik di atas kertas dalam hal kinerja kasus terbaik dan terburuk (MergeSort tidak memiliki kelemahan Achilles terkait dengan pemilihan elemen seperti QuickSort, dan kasing terbaiknya adalah daftar yang hampir disortir sementara itu seringkali yang terburuk dari QuickSort). Saya ragu manfaat multithreading pada awalnya dipertimbangkan, tetapi implementasi saat ini mungkin multithreaded.
sumber
List<T>.Sortdi .NET menggunakan metode asli yang diterapkan di CLR (jika Anda tidak menggunakan pembanding kustom), tetapi tidak memiliki dependensi pada pustaka OS.Tim pengembangan yang berbeda di dua perusahaan yang berbeda sampai pada kesimpulan yang berbeda mengenai kasus penggunaan yang biasa untuk kerangka kerja dan komponen mereka dan telah memutuskan untuk menerapkannya.
Pada dasarnya, setiap perusahaan melakukan analisis mereka, melihat basis klien mereka dan membuat keputusan yang berbeda sesuai.
Anda tidak dapat mengharapkan analisis oleh berbagai perusahaan dan tim, menggunakan berbagai asumsi dan data mentah untuk sampai pada kesimpulan yang sama.
sumber
Pertanyaan ini agak ketinggalan zaman, karena Java sekarang menggunakan Timsort (per Java 7)
Dari algoritma spesifik yang disebutkan:
Quicksort memiliki kinerja terburuk pada O (n ^ 2), tetapi sedikit lebih ringan / kurang memakan memori sehingga menawarkan kinerja yang lebih baik dalam kasus biasa.
Mergesort telah menjamin kinerja kasus terburuk di O (n log n), tetapi membawa lebih banyak kebutuhan overhead dan memori. Itu juga secara otomatis stabil (yaitu mempertahankan elemen yang sama dalam urutan yang sama).
Para desainer Jawa tampaknya secara umum sedikit lebih konservatif / fokus pada "hal yang benar" sehingga tidak mengejutkan bahwa mereka memilih Mergesort dari keduanya karena menawarkan jaminan yang lebih baik.
Tidak yakin mengapa Microsoft memilih Quicksort, mungkin mereka berpikir itu akan membuat mereka terlihat lebih baik di beberapa benchmark mikro?
sumber