Dalam pengolahan data, sorting atau pengurutan data menjadi hal yang penting dan harus dilakukan. Dengan kebutuhan pengolahan data termasuk sorting maka banyak metode-metode yang digunakan dalam pengurutan data seperti:
- Bubble Sort,
- Bidirectional Bubble Sort,
- Selection Sort,
- Insertion Sort,
- Inplace Merge Sort,
- Double Storage Merge Sort,
- Comb Sort 11,
- Heap Sort,
- Raix Sort
- Exchange Sort
- Merge Sort, dsb.
Namun kali ini kita akan membahas Radix sort, dimana Radix Sort ini merupakan algoritma sorting yang cukup banyak digunakan. Lalu apa itu Radix Sort?
Pengertian
Radix Sort adalah algortima atau metode pengurutan (sorting) tanpa pembandingan dengan kata lain, sorting Non-Comparasion sort dimana dalam prosesnya tidak melakukan perbandingan antar data. Kata radix bermakna harafiah posisi dalam angka.
Di mana sederhananya, dalam representasi desimal, radix adalah digitnya. Dalam implementasinya, Radix Sort merupakan algoritma pengurutan yang cepat, mudah, dan sangat efektif. Namun banyak yangmengira bahwa algoritma radix memiliki banyak batasan di mana untuk kasus-kasus tertentu tidak dapat dilakukan dengan algoritma ini, seperti pengurutan bilangan pecahan dan bilangan negative.
Berdasarkan urutan pemrosesan radixnya, Radix Sort terbagi 2 macam, yaitu:
- LSD (Least Significant Digit), di mana pemrosesan dimulai dari radix yang paling tidak signifikan. Sorting dilakukan dengan cara mengurutkan nilai-nilai input berdasarkan digit terjahir ke digit pertama.
- MSD (Most Significant Digit), di mana pemrosesan dimulai dari radix yang paling signifikan. Sorting dilakukan dengan cara mengurutkan nilai-nilai input berdasarkan digit pertama, lalu dilanjutkan lagi berdasarkan radix keuda dan seterusnya.
Cara Kerja
Dalam artikel jurnal yang ditulis sabarudi et al, Proses dasar Radix Sort adalah mengkategorikan data-data menjadi sub kumpulan data sesuai dengan nilai radix-nya (kategori tertentu), dimana dalam tiap kategorinya dilakukan pengklasifikasian lagi dan seterusnya sesuai dengan kebutuhan mengkonkatenasinya, dan subkategori-subkategori tersebut digabungkan kembali, yang secara dilakukan hanya dengan metode sederhana concatenation.
Contoh Algoritma Radix Sort
Terdapat data sebagai berikut:
Lalu buat bucket untuk menyimpan data sementara dari data diatas. Dengan mengurutkan dari radix (digit) atau digit satuan dan dimasukkan ke dalam bucket yang sesuai angka radix.
Setalah itu tulis hasil sorting
81 33 94 05 48 69
Dan lanjutkan sorting dengan digit depanya (digit puluhan)
Lalu dijadikan satu lagi dalam array
05 33 48 05 69 94
Dan itulah hasil setelah diurutkan menggunakan radix sort. Jika masih ada digit depanya (digit ratusan) maka tetap lanjut, cara seperti sebelumnya.
