Perbandingan algoritma pengurutan
Tidak ada satu algoritma pengurutan yang selalu tercepat. Ada yang sederhana tapi lambat, ada yang cepat pada data acak tapi tersandung pada data terurut, dan ada yang sama sekali bukan pengurutan perbandingan. Membalapkan kedelapannya pada daftar yang sama menunjukkan perbedaannya sekilas.
Tiga keluarga
Bubble sort, selection sort, dan insertion sort adalah pengurutan sederhana. Ketiganya membandingkan dan menukar nilai yang berdekatan dan butuh waktu sebanding dengan n² pada daftar acak. Merge sort, quicksort, dan heap sort membagi kerja dengan cerdik dan butuh waktu sebanding dengan n log n, yang merupakan hasil terbaik yang bisa dicapai pengurutan yang hanya boleh bertanya mana dari dua nilai yang lebih besar. Radix sort dan counting sort melewatkan pertanyaan itu sepenuhnya: keduanya memakai digit atau nilai itu sendiri, yang hanya berhasil untuk kunci seperti bilangan bulat kecil.
Mengukur kerja
Adu pengurutan menghitung satu operasi untuk setiap perbandingan, setiap pembacaan digit atau nilai, dan setiap penukaran atau pemindahan. Pada 40 nilai acak, hasilnya sekitar 120 untuk counting sort, 240 untuk radix sort, 260 untuk quicksort, 380 untuk merge sort, 490 untuk heap sort, masing-masing sekitar 820 untuk selection sort dan insertion sort, dan lebih dari 1.100 untuk bubble sort. Komputer sungguhan juga memperhitungkan memori: dalam praktik quicksort biasanya lebih cepat daripada yang ditunjukkan hitungannya, dan heap sort lebih lambat, karena cara keduanya bergerak melalui daftar.
Masukan itu penting
Pada daftar yang hampir terurut, insertion sort hanya butuh sekitar 50 operasi untuk 40 nilai dan bubble sort sekitar 90, karena setiap nilai dekat dengan tempatnya. Pada daftar terbalik, keduanya butuh 1.560, kasus terburuk mereka. Selection sort, heap sort, merge sort, radix sort, dan counting sort hampir tidak terpengaruh urutan. Quicksort dengan median dari tiga menangani daftar terurut dan terbalik dengan baik, tetapi dengan pivot yang naif, daftar terurut justru menjadi kasus terburuknya. Sedikit nilai unik memperlambat quicksort, karena nilai yang sama semuanya masuk ke satu sisi.
Memori dan stabilitas
Bubble sort, selection sort, insertion sort, quicksort, dan heap sort bekerja di tempat (in place), dengan sedikit atau tanpa memori tambahan. Merge sort, radix sort, dan counting sort butuh buffer sepanjang daftar. Pengurutan yang stabil menjaga nilai yang sama tetap dalam urutan aslinya: bubble sort, insertion sort, merge sort, radix sort, dan counting sort stabil, sedangkan selection sort, quicksort, dan heap sort tidak. Stabilitas penting saat Anda mengurutkan data berdasarkan satu kolom lalu kolom lainnya.
Mana yang dipakai
Dalam praktik Anda memakai pengurutan bawaan bahasa pemrograman Anda: biasanya Timsort, merge sort yang memakai insertion sort untuk potongan pendek dan cepat pada data yang sebagian terurut, atau introsort, quicksort yang beralih ke heap sort dan memakai insertion sort untuk bagian kecil. Untuk banyak kunci bilangan bulat kecil, counting sort atau radix sort bisa mengalahkan keduanya. Bubble sort dan selection sort terutama alat pengajaran.
Jelajahi
Buka adu pengurutan dan tekan Putar. Setiap lintasan adalah satu pengurutan pada daftar yang sama; angka di kanan menghitung operasinya, dan lintasan berubah hijau saat selesai. Coba daftar yang hampir terurut, yang terbalik, dan yang dengan sedikit nilai unik, lalu amati urutan finisnya berubah. Setiap pengurutan juga punya aplikasinya sendiri, tempat Anda bisa menelusurinya langkah demi langkah secara rinci.
Pertanyaan yang sering diajukan
Apa algoritma pengurutan tercepat?
Untuk data umum, quicksort dan merge sort (serta hibrida yang dibangun di atasnya, seperti introsort dan Timsort) rata-rata tercepat, dengan n log n. Untuk kunci bilangan bulat kecil, counting sort dan radix sort lebih cepat lagi. Untuk daftar pendek atau hampir terurut, insertion sort menang.
Mengapa tidak ada pengurutan perbandingan yang bisa mengalahkan n log n?
Daftar n nilai bisa punya n! urutan, dan setiap perbandingan punya dua hasil, jadi dalam kasus terburuk dibutuhkan setidaknya log₂(n!) perbandingan untuk membedakan semuanya. Itu sekitar n log₂ n. Radix sort dan counting sort menghindari batas ini karena tidak membandingkan.
Algoritma pengurutan mana yang stabil?
Bubble sort, insertion sort, merge sort, radix sort, dan counting sort stabil dalam bentuk biasanya. Selection sort, quicksort, dan heap sort tidak, karena memindahkan nilai ke tempat yang jauh.
Pengurutan mana yang butuh memori tambahan?
Merge sort, radix sort, dan counting sort butuh buffer kira-kira sepanjang daftar. Bubble sort, selection sort, insertion sort, dan heap sort hampir tidak butuh, dan quicksort hanya sedikit untuk rekursinya.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Mulai adu pengurutan