Inti dari pertanyaan ini adalah bukan untuk memperdebatkan kelebihan ini atas algoritma pengurutan lainnya - tentu saja ada banyak pertanyaan lain yang melakukan ini. Pertanyaan ini tentang nama. Mengapa Quicksort disebut "Quicksort"? Tentu, ini "cepat", sebagian besar waktu, tetapi tidak selalu. Kemungkinan degenerasi menjadi O (N ^ 2) sudah diketahui. Ada berbagai modifikasi untuk Quicksort yang mengurangi masalah ini, tetapi yang membawa kasus terburuk ke O dijamin (n log n) tidak secara umum disebut Quicksort lagi. (mis. Introsort).
Saya hanya ingin tahu mengapa dari semua algoritma penyortiran yang terkenal, ini adalah satu-satunya yang pantas untuk nama "cepat", yang menggambarkan bukan bagaimana cara kerjanya, tetapi seberapa cepat (biasanya). Mergesort disebut demikian karena menggabungkan data. Heapsort disebut itu karena menggunakan heap. Introsort mendapatkan namanya dari "Introspektif", karena memantau kinerjanya sendiri untuk memutuskan kapan harus beralih dari Quicksort ke Heapsort. Demikian pula untuk semua yang lebih lambat - Bubblesort, Jenis penyisipan, Jenis pilihan, dll. Mereka semua diberi nama untuk cara kerjanya. Satu-satunya pengecualian lain yang bisa saya pikirkan adalah "Bogosort", yang sebenarnya hanya lelucon yang tidak pernah benar-benar digunakan oleh siapa pun dalam praktik. Mengapa Quicksort tidak menyebut sesuatu yang lebih deskriptif, seperti "Urut partisi" atau "Urut pivot", yang menggambarkan apa yang sebenarnya dilakukannya? Ini bahkan bukan kasus "sampai di sini dulu". Mergesort dikembangkan 15 tahun sebelum Quicksort. (1945 dan 1960 masing-masing menurut Wikipedia)
Saya kira ini lebih merupakan pertanyaan sejarah daripada pertanyaan pemrograman. Saya hanya ingin tahu bagaimana ia mendapatkan nama - apakah itu pemasaran yang bagus?
sumber
What's in a name? that which we call a rose By any other name would smell as sweet;
Itu atau secepatnya. Selain itu, kemungkinan degenerasi menjadi O (N ^ 2) memiliki peluang kecil terjadi, dan N LogN cukup baik untuk suatu algoritma, meskipun pada kenyataannya kita memiliki algoritma yang lebih cepat saat ini. Selain itu, pada saat sesuatu yang lebih cepat muncul, semuanya sudah terlambat, semua orang sudah menyebutnya Quicksort!Jawaban:
Pada tahun 1962, penelitian tentang algoritma pengurutan tidak semaju sekarang dan ilmuwan komputer Tony Hoare menemukan algoritma baru yang lebih cepat daripada yang lain sehingga ia menerbitkan makalah yang disebut Quicksort dan ketika makalah itu dikutip, judulnya tetap.
Mengutip abstrak:
sumber
Saya percaya bahwa itu awalnya disebut Hoare Sort setelah penemu tetapi namanya berubah cukup awal karena Hoare terdengar sedikit dekat dengan pelacur dalam bahasa Inggris. Mengenai mengapa mereka memilih "cepat" daripada yang lain, saya tidak yakin.
sumber
Saya percaya itu karena, pada saat ditemukan, itu jauh lebih cepat daripada semua (atau, lebih tepatnya, sebagian besar, karena kecepatan juga sangat tergantung pada jenis data dan dalam beberapa kasus algoritma lain menjadi jauh lebih cepat daripada quicksort) dari algoritma di luar sana.
Jadi ya, ini historis (saya tidak tahu persis sejarah itu, bagaimanapun ...)
Tapi saya setuju bahwa namanya seharusnya berisi petunjuk tentang algoritma ...
sumber