Quicksort dan tidak repot?

Terutama ketika menulis aplikasi 'standar' (non-HPC), apakah Anda mempertimbangkan algoritma pengurutan apa yang harus dipilih, atau hanya menyelesaikan dengan quicksort (yang kebanyakan perpustakaan hanya memanggil semacam)? Untuk beberapa hal mungkin menguntungkan dalam situasi tertentu, tetapi di sisi lain optimasi yang tepat memerlukan waktu untuk menganalisis masalah dan membuat tolok ukur.

Secara umum, menggunakan metode default kecuali ada kebutuhan khusus untuk melakukan sesuatu yang lebih eksotis membuat semuanya jauh lebih mudah dibaca / dimengerti IMHO.

Jika Anda mengalami (atau dalam beberapa kasus, sangat curiga) bahwa Anda memiliki masalah kinerja, inilah saatnya untuk menambah kompleksitas.

Di sisi lain, jika Anda menggunakan bahasa yang cukup rendah sehingga tidak ada semacam bawaan untuk jenis objek yang Anda butuhkan untuk mengurutkan mencoba memilih satu atau dua yang mencakup semua pangkalan Anda dan mengimplementasikannya.

Selalu panggil rutin perpustakaan yang disediakan, kecuali Anda memiliki alasan yang sangat, sangat baik untuk tidak melakukannya (dan Anda perlu mendokumentasikan mengapa demikian).

Ini karena algoritma pengurutan sulit dilakukan dengan benar. Ada bug di quicksort Java dengan kumpulan data yang sangat besar, yang diidentifikasi, diperbaiki, dan dikirim ke pelanggan oleh Sun, jadi Anda tidak harus melakukannya.

Juga jenis default di Java 7 telah ditingkatkan ke yang lebih baru, jenis yang lebih baik. Juga gratis.

Kecuali jika jenis bawaannya terbukti tidak cukup baik untuk Anda, tetaplah menggunakannya.

Di sebuah konferensi pernah saya mendengar cerita yang bagus tentang ini.

Di Microsoft seseorang sedang menulis aplikasi VB (c. VB 3) dan mengirimkan banyak orang mengatakan bahwa ia memiliki banyak nilai dan ia ingin mereka muncul di kotak kombo dalam rangka, bagaimana ia harus mengatasinya.

Semua orang menyelam untuk buku teks sains komputer lama mereka, mencari rutinitas yang sangat efisien dan mengirimkannya ke Visual Basic dan mengirimkannya kepadanya. Satu orang baru saja mengirim kembali "berapa nilai dalam kotak kombo?".

"Sekitar 50" terdengar jawabannya.

"Cukup atur properti yang diurutkan ke TRUE".

Dalam 99,9999% penyortiran contoh paling baik dilakukan dengan menggunakan perpustakaan, kontrol atau dalam SQL pilih karena perbedaan kinerja antara rutin perpustakaan dan apa pun yang Anda tulis akan diabaikan dan biaya overhead upaya dan pemeliharaan akan secara besar-besaran melebihi konsekuensinya.

Inilah saatnya untuk mengeluarkan kutipan klasik tentang optimasi prematur. Dalam kebanyakan kasus, itu benar-benar tidak masalah. Heck, dengan kecepatan CPU hari ini, Anda mungkin bisa menyortir sebagian besar set data dan tidak terlalu memperhatikan. Tetapi ketika Anda mengurutkan set data yang sangat besar, dan kinerja sortir mulai menjadi masalah, maka Anda harus melihat opsi lain.

Meskipun itu jelas tidak masalah dengan bit dan rentang waktu. Saya menemukan semacam penggabungan agar lebih mudah ditulis dan dipahami daripada quicksort. Jadi jika saya akan menulis algoritma pengurutan saya sendiri saya akan menggunakannya.

Setidaknya di perpustakaan yang ditulis dengan kompeten, saya berharap built-in sortdiimplementasikan sebagai Introsort daripada hanya Quicksort. Perbedaannya jarang penting, tetapi Introsort menghilangkan kinerja terburuk Quicksort dengan efek minimal pada kasus yang lebih umum.

Namun, untuk menjawab pertanyaan Anda: ya - itulah yang biasanya Anda mulai dengan, dan sampai / kecuali Anda memiliki hasil profiler yang menunjukkan bahwa itu adalah masalah, di situlah seharusnya tetap ada.