Radix Sort

Pengertian Sorting
Algoritma adalah kumpulan langkah sistematis untuk memperoleh hasil yang diinginkan. Salah satu contoh dari algoritma adalah Sorting (pengurutan). Sorting dapat didefinisikan sebagai pengurutan sejumlah data berdasarkan nilai tertentu. Pengurutan dapat dilakukan dari nilaiterkecil ke nilai terbesar (ascending) atau sebaliknya




Sorting dapat dibedakan menjadi dua yaitu Comparasion Sort (Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort) dan Non-Comparasion Sort (Radix Sort, Counting Sort). Comparasion Sort / penggurutan dengan pembandingan adalah algoritma yang dalam proses pengurutannya melakukan pembandingan antar data. Non-Comparasion Sort / pengurutan tanpa pembandingan adalah algoritma pengurutan dimana dalam prosesnya tidak melakukan perbandingan antar data.

Radix Sort
Radix Sort merupakan salah satu algoritma Non-Comparasion Sort (pengurutan tanpa pembandingan). Proses ynang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu, dan tiap kategori dilakukan pengklasifikasian lagi, dan seterusnya sesuai kebutuhan, lalu subkategori-kategori tersebut digabungkan kembali.
Secara harfiah Radix dapat diartikan sebagai posisi dalam angka, karena metode ini pertamakalinya mengurutkan nilai-nilai input berdasarkan radix pertamanya, lalu pengurutan dilakukan berdasarkan radix keduanya, dan begitu seterusnya. Pada system decimal, radix adalah digit dalam angka decimal.
Berikut ini adalah contoh penggunaan algoritma radix sort untuk pengurutan sebuah kumpulan bilangan bulat positif, dengan jumlah digit maksimal 3 :
121 076 823 367 232 434 742 936 274
Pertama kali data dibagi-bai sesuai dengan digit terkanan :
121 076 823 367 232 434 742 936 274
Sehingga dapat ditabelkan :

Kategori Digit Isi
0 -
1 121
2 232, 742
3 823
4 434, 274
5 -
6 076, 936
7 367
8 -
9 -
Kategori Digit Isi
0 -
1 -
2 121, 823
3 232, 434, 936
4 742
5 -
6 367
7 274, 076
8 -
9 -
Tabel 1.1 Hasil Pengkategorian Pertama Tabel 1.2 Hasil Pengkategorian Kedua
Hasil pengkategorian tersebut kemudian digabung kembali menjadi :
121 232 274 823 434 274 076 936 367

Kemudian dilakukan pengkategorian lagi berdasar digit kedua :
121 232 274 823 434 274 076 936 367

Sehingga penabelannya dapat dilihat pada table 1.2
Hasil pengkategorian tersebut kemudian digabung kembali menjadi :
121 823 232 434 936 742 367 274 076

Kemudian langkah ketiga, dilakukan pengkategorian lagi berdasar digit ketiga (terakhir) :
121 823 232 434 936 742 367 274 076

Kategori Digit Isi
0 076
1 121
2 232, 274
3 367
4 434
5 -
6 -
7 742
8 823
9 936
Tabel 1.3 Hasil Pengkattegorian Ketiga

Yang kemudian hasil akhirnya dapat dituliskan :
076 121 232 274 367 434 742 823 936


Pada hasil akhir dapat dilihat bahwa data telah terurut dengan menggunakan metode radix sort. Berikut ini adalah rumus Radix Sort :

Dari langkah-langkah yang telah dilakukan dalam proses pengurutan menggunakan radix sort, jelas tampak bahwa radix sort termasuk algoritma pengurutan tanpa pembanding. Dengan sifatnya yang melihat digit-digit angka sebagai pengontrolnya, Radix Sort dapat diimplementasikan dalam pengurutan bilangan decimal dan bilangan bit. Namun dalam penggunaannya radix sort bisa dimodifikasi sehingga bisa digunakan untuk menggurutkan data-data negatif dan pecahan.
Kelebihan yang dimiliki Radix Sort antara lain adalah merupakan algoritma pengurutan yang cepat, mudah, dan sangat efektif. Namun penggunaannya terbatas pada kasus-kasus tertentu dan memerlukan memori tambahan dalam prosesnya.