Radix sort
Radix sort adalah yang paling lain di antara algoritma pengurutan: ia tidak pernah bertanya mana dari dua nilai yang lebih besar. Ia membaca angka digit demi digit dan mengurutkannya satu digit setiap kali, menggunakan sepuluh ember. Idenya lebih tua daripada komputer: begitulah cara kerja mesin pengurut kartu berlubang.
Idenya
Urutkan angka-angka berdasarkan digit satuannya saja. Lalu urutkan berdasarkan digit puluhan, tetapi dengan cara yang menjaga angka berdigit puluhan sama tetap dalam urutan dari putaran pertama. Lalu berdasarkan ratusan, dengan cara yang sama. Setelah putaran terakhir daftar terurut: ratusan menentukan lebih dulu, angka dengan ratusan sama sudah urut menurut puluhannya, dan yang puluhannya juga sama sudah urut menurut satuannya.
Satu putaran, dengan ember
Setiap putaran memakai sepuluh ember, satu untuk tiap digit 0 sampai 9. Telusuri daftar dari awal ke akhir dan pindahkan setiap angka ke ember untuk digitnya, di belakang angka yang sudah ada di sana. Lalu kosongkan ember-ember kembali ke daftar secara berurutan, ember 0 lebih dulu. Memindahkan angka sesuai urutan daftar dan menambahkannya di belakang ember itulah yang membuat putaran stabil. Aplikasi ini menghitung dulu jumlah angka untuk tiap digit, sehingga ember-ember bisa berjajar dalam satu baris, masing-masing mulai tepat setelah ember sebelumnya: itulah counting sort pada satu digit.
Sebuah contoh
Ambil 170, 45, 75, 90, 802, 24, 2, 66. Berdasarkan digit satuan: 170, 90, 802, 2, 24, 45, 75, 66. Berdasarkan digit puluhan: 802, 2, 24, 45, 66, 170, 75, 90; perhatikan bahwa 802 dan 2, keduanya dengan digit puluhan 0, mempertahankan urutan dari putaran pertama. Berdasarkan digit ratusan: 2, 24, 45, 66, 75, 90, 170, 802. Tiga putaran atas delapan angka: 24 digit dibaca dan 48 pemindahan, tanpa satu perbandingan pun.
Seberapa cepat?
Setiap putaran membaca satu digit dari setiap angka dan memindahkan setiap angka dua kali, jadi untuk n angka dengan d digit, kerjanya tumbuh sebanding n · d. Pengurutan berbasis perbandingan butuh setidaknya sekitar n log₂ n perbandingan dalam kasus terburuk, karena harus membedakan n! kemungkinan urutan dengan satu pertanyaan ya-atau-tidak setiap kali. Radix sort tidak terikat batas itu, karena tidak pernah mengajukan pertanyaan semacam itu. Untuk banyak kunci pendek, seperti satu juta angka di bawah 1.000, tiga putaran jauh lebih ringan daripada sekitar 20 juta perbandingan yang dibutuhkan pengurutan berbasis perbandingan. Untuk kunci panjang atau sedikit nilai, keunggulan itu hilang.
LSD dan MSD, serta sejarahnya
Versi yang ditampilkan di sini dimulai dari digit paling tidak signifikan (LSD). Cara sebaliknya, digit paling signifikan lebih dulu (MSD), membagi daftar ke dalam ember berdasarkan digit pertama dan mengurutkan tiap ember secara terpisah, yang cocok untuk string dengan panjang berbeda. Radix sort berawal dari mesin pengurut kartu berlubang yang menyusul mesin tabulasi Herman Hollerith untuk sensus AS 1890: mesin pengurut menjatuhkan setiap kartu ke salah satu dari sepuluh kantong menurut lubang di satu kolom, dan operator menjalankan tumpukan kartu sekali per kolom, mulai dari kolom terakhir.
Jelajahi
Buka aplikasi dan tekan Langkah. Setiap putaran lebih dulu menghitung digit, yang menandai ember 0 sampai 9 di baris di bawah daftar. Lalu angka-angka jatuh ke embernya satu per satu, dengan ember aktif disorot, dan disalin kembali. Ketik angka sendiri hingga 999, seperti contoh di atas, untuk melihat ketiga putaran.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu radix sort?
O(n · d) untuk n kunci dengan d digit dalam basis tetap, ditambah biaya ember untuk tiap putaran. Ia butuh memori tambahan O(n) untuk buffer tempat ember berada.
Apakah radix sort stabil?
LSD radix sort harus stabil: ia hanya berhasil karena setiap putaran menjaga nilai dengan digit yang sama dalam urutan kedatangannya. Karena itu hasil akhirnya juga stabil.
Bisakah radix sort menangani angka negatif atau desimal?
Tidak secara langsung, tetapi bisa dengan trik: geser angka negatif agar semuanya positif, atau urutkan secara terpisah lalu balik urutannya. Bilangan floating-point bisa diurutkan berdasarkan pola bitnya setelah sedikit transformasi.
Mengapa memakai basis 10?
Karena mudah diikuti. Komputer biasanya mengurutkan 8 atau 16 bit setiap kali, jadi angka 32-bit butuh empat atau dua putaran, dengan 256 atau 65.536 ember.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba radix sort