Radix Sort

Bahasan kali ini bukan sesuatu yang berat, yaitu sekedar radix sort.

Orang-orang yang telah menguasai algoritma pengurutan tingkat lanjut pasti tahu tentang jenis pengurutan ini. Algoritmanya sendiri memiliki konsep yang sederhana. Namun di balik konsep sederhana itu, implementasinya mungkin tidak semudah yang dibayangkan. Alasan saya menulis topik ini adalah memperkenalkan implementasinya, yang ternyata menggunakan stable counting sort.

Pengurutan ini cukup unik, untuk mengurutkan N angka yang memiliki paling banyak d digit, kompleksitasnya adalah O(Nd). Untuk nilai d yang kurang dari log N, algoritma ini lebih cepat dari pengurutan O(N log N).

Supaya semua orang berada di posisi yang sama, saya akan mengulas konsep radix sort terlebih dahulu.

---

Konsep

Misalkan kita memiliki angka-angka berikut untuk diurutkan:

542
215
341
152
78
269

Pada radix sort, secara bertahap kita mengurutkan datanya dari digit paling belakang. Berikut hasilnya ketika digit paling belakang terurut:

3 4 1
5 4 2
1 5 2
2 1 5
0 7 8
2 6 9

Agar lebih mudah dilihat, saya menyisipkan spasi di antara digit-digit angkanya.

Hal yang perlu diperhatikan adalah satu tahap pengurutan ini harus stable. Artinya, ketika terdapat elemen yang sama, elemen yang lebih dulu muncul pada data harus muncul lebih awal pula pada hasil pengurutan.

Pada contoh di atas, angka 542 dan 152 sama-sama memiliki angka 2 sebagai digit paling akhir. Berhubung 542 muncul lebih awal, maka pada hasil pengurutannya 542 juga harus muncul lebih awal dari 152.

Ulangi tahapan pengurutan yang sama pada digit kedua dari belakang:

2 1 5
3 4 1
5 4 2
1 5 2
2 6 9
0 7 8

Terakhir, pada digit ketiga dari belakang (alias paling depan):

0 7 8
1 5 2
2 1 5
2 6 9
3 4 1
5 4 2

Kini data kita telah terurut:

78
152
215
269
341
542

Konsepnya sederhana bukan?
Memang mudah, tetapi Ketika baru belajar saya bingung bagaimana mengimplementasikannya.

---

Implementasi

Titik berat algoritma ini sebenarnya ada pada pengurutan per tahapannya. Pengurutan ini harus bekerja dalam O(N), dan bersifat stable. Counting sort merupakan pengurutan yang cocok untuk tugas ini.

Counting sort perlu dimodifikasi sedikit. Misalkan kita melakukan pengurutan tahap pertama, yaitu digit paling akhir. Buat tabel frekuensi untuk digit-digit yang muncul:

542
215
341
152
 78
269

digit      0 1 2 3 4 5 6 7 8 9
frekuensi  0 1 2 0 0 1 0 0 1 1

Kemudian buat jumlahan kumulatifnya:

digit      0 1 2 3 4 5 6 7 8 9
frekuensi  0 1 2 0 0 1 0 0 1 1
kumulatif  0 1 3 3 3 4 4 4 5 6

Dari jumlahan kumulatif ini, kita memiliki informasi yang *secara mengejutkan* penting.

Perhatikan digit 9. Nilai jumlahan kumulatifnya adalah 6. Hal ini berarti, elemen dengan digit terakhir 9 (269) akan berada di posisi ke-6 setelah diurutkan.

Hal serupa juga dapat diamati untuk digit 5 dan 8, yang mana masing-masing 215 dan 78 akan berada di posisi 4 dan 5 setelah diurutkan.

Untuk menariknya, perhatikan digit 2. Jumlahan kumulatifnya adalah 3, yang sebenarnya berarti elemen dengan digit terakhir 2 yang paling belakang, akan ditempatkan di posisi ke-3. Apabila kita sudah menempatkan elemen dengan digit terakhir 2 yang paling belakang (yaitu 152) di posisi ke-3, elemen lainnya dengan digit terakhir 2 (yaitu 542) perlu ditempatkan di posisi sebelumnya, yaitu posisi ke-2. Teknik ini dapat digunakan untuk memastikan elemen yang muncul lebih akhir, ditempatkan di posisi lebih akhir pula pada hasil pengurutan, sehingga memenuhi sifat stable sort.

Mulai dari elemen terakhir array ke yang pertama, tentukan di indeks keberapa mereka perlu ditempatkan.

Dengan informasi ini, kita dapat menulis sebuah for loop dari belakang ke depan, sambil mencari hasil pengurutan saat ini. Nilai kumulatif lainnya untuk frekuensi yang 0 tentu saja dapat diabaikan.

Cukup ulangi langkah pengurutan ini sampai tidak ada digit yang perlu diurutkan. Didapatkanlah algoritma pengurutan O(Nd).

---

Penutup

Untuk kompetisi, radix sort mungkin tidak akan Anda gunakan untuk mengurutkan angka seperti ini. Namun radix sort dapat membantu Anda untuk mengurutkan string (cukup ganti per digit dengan per karakter). Lebih jauh lagi, radix sort menjadi kunci pada algoritma pembuatan suffix array O(N log N). Apa itu suffix array mungkin akan saya jelaskan di lain kesempatan, intinya itu adalah struktur data string yang memungkinkan berbagai operasi pada string secara efisien.

Tentu saja dengan mengetahui radix sort lebih lanjut, Anda lebih kaya dengan pengetahuan. Semoga ini bermanfaat bagi Anda!