Algoritma Radix Sort Pada Java

Radix Sort

Radix Sorting adalah salah satu algoritma Non-Comparasion Sort (pengurutan tanpa pembandingan) dengan metode sorting yang mana mengatur pengurutan nilai tanpa melakukan beberapa perbandingan pada data yang dimasukkan. Secara harfiah, radix dapat diartikan sebagai posisi dalam angka. Pada sistem desimal, radix adalah digit dalam angka desimal. Seperti contoh, angka “26” mempunyai 2 digit yaitu 2 dan 6. 

Radix sort tidak dapat digunakan pada kasus-kasus tertentu seperti pengurutan bilangan pecahan, bilangan negatif, adanya kompleksitas bit dan word, dan pengurutan pada multiple keys. Radix sort hanya bisa digunakan pada bilangan integer, untuk bilangan pecahan, bisa dilakukan dengan perantara bucket sort atau metode berbasis perbandingan yang lain. Dalam perilakunya yang melihat digit-digit angka sebagai pengontrolnya, Radix Sort dapat dimplementasikan dalam pengurutan bilangan desimal dan bilangan bit.

Implementasi dalam bilangan desimal misalkan terdapat 5 list bilangan dengan angka yang berbeda. Pertama tentukan urutan digit terakhir pada bilangan, dilakukan dari digit terakhir sampai pada digit pertama. Digit yang dicetak merah menunjukkan digit mana yang sedang berjalan dalam proses pengurutan, setelah itu baru bisa dilihat hasilnya.

Contoh implementasi radixsort :

import java.io.BufferedInputStream;
import java.io.*;

public class radix {static void radixsort (int a[], int d)
{
int bmat[][], c[], e=1;
int i, j, k, m, digit, row, col;

bmat = new int [a.length][10];
c    = new int [10];

for (m=1; m<=d; m++){
for (i=0; i<10; i++){
              c[i]=-1;
}
for (i=0; i<a.length; i++){
              digit = (a[i]/e)%10;
             c[digit]++;
             row   = c[digit];
             col   = digit;
             bmat[row][col]=a[i];
}
k=-1;
for (i=0; i<10; i++){
if(c[i]!=-1){
for (j=0; j<=c[i]; j++){
k++;
a[k]=bmat[j][i];
}
}
}
e=e*10;
}
}
public static void main(String[] args) throws Exception{
BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Berapa banyak bilangan untuk di urutkan ?”);
int n =Integer.parseInt(inp.readLine());

int a[]=new int[n];
for (int i=0; i<n; i++)
{
             System.out.println(“Inputkan Nilai “+(i+1)+” : “);
             a[i]=Integer.parseInt(inp.readLine());
}

radixsort (a,3);
             System.out.println(“\n”+”Array Terurut: “);

for (int i=0; i<n; i++)
{
             System.out.print(a[i]+” “);
}
             System.out.println();
}

Hasil :