Radix sort adalah salah satu metoda sorting yang berdasarkan digit (subdata) pembentuk bilangan.
Ada 2 jenis radix sort :
*LSD(Least Significant Digit) : sort dari digit yang terkecil.
*MSD(Most Significant Digit) : sort dari digit yang terbesar.
Nah, radix ini menggunakan sistem bucket, bucket itu sendiri adalah tempat untuk menampung hasil sorting sementara. Bucket itu di implementasikan dengan array of linked list. Banyaknya bucket bergantung pada radixnya, misalkan menggunakan alfabet(ada 26 karakter) berarti akan ada 26 bucket.
- Untuk memulai radix sort, langkah ke-1 adalah mencari tahu angka terbesar untuk menentukan ada berapa ronde. misalkan ada : 81,94,411,66,312,535,717,295,958,328,150,697
Angka terbesar adalah 958, untuk menghitung jumlah ronde :
max=958/10 -> max=95 -> JumRonde = 1
max=95/10 -> max=9 -> JumRonde = 2
max=9/10 -> max=0 -> JumRonde = 3
perulangan selesai dikarenakan max=0.
- Nah langkah ke-2 yaitu ekstrasi nilai digit. Kita harus mencari digit satuan pada putaran pertama,digit puluhan pada putaran kedua, dan seterusnya.
contoh :
putaran pertama(ronde pertama):
Pada ronde pertama digit yang kita ambil adalah digit satuan, jadi misal angka tersebut 81 maka satuan nya 1, maka dimasukan kedalam bucket index 1.
94 = 4 maka dimasukan ke index ke 4.
150 = 0 maka dimasukan ke index ke 0.
Hal tersebut dilakukan sampai semua element array masuk ke dalam bucket.
Contoh Koding:
for(i=0;i<JumRonde;i++){
pembagi = pow(10,i);
for(j=0;j<JumData;j++){
nilaidigit=(arr[j]/pembagi)%10;
}
}
- Langkah ke-3 Misalkan disaat kita memasukan element kedalam bucket namun terdapat element kedua yang lokasi array nya sama dengan element sebelumnya maka nilai element sebelumnya akan hilang. Maka dari itu perlu dibuat array of link list. Yaitu mengaitkan simpul ke bucket. Disini akan dibuat simpul untuk dikaitkan pada ujung kanan bucket sesuai dengan digitnya. Jika bucket yang bersangkutan masih bernilai NULL, maka simpul tersebut menjadi simpul pertama. Jika tidak maka perlu ditelusuri dahulu simpul terakhir dan akan dikaitkan dengan simpul baru.
contoh:
B[0]=90
B[1]=81
…..
…..
Kemudian ada element yg baru adalah 10, maka:
B[0]=90;0
B[1]=81
…….
…….
Contoh Koding:
struct tdata{
int data;
struct tdata *next;
};
……..
node = (struct tdata*) malloc(sizeof(struct tdata));
node->data = arr[j];
node->next=NULL;
nilaidigit=(arr[j]/pembagi)%10;
if(bucket[sisa]==NULL) bucket[sisa]=node;
else{
curr=bucket[sisa];
while(curr->next!=NULL) curr = curr->next;
curr->next = node;
}
- Langkah ke-4 adalah menyalin isi simpul pada bucket ke array. Nah ketika data sudah di alokasikan ke bucketnya, isi bucket disalin kembali ke array semula dari simpul pertama bucket pertama hingga simpul terakhir bucket terakhir secara berurut.
contoh:
B[0] = 20;40;10;230
B[1] = 21;121;1;51
…….
……
Sehingga menjadi A[…] = 20;40;10;230;21;121;1;51;…..
Contoh Koding:
idx = 0;
for(j=0;j<10;j++){
curr=bucket[j];
while(curr){
arr[idx++]=curr->data;
curr=curr->next;
}
}
- Langkah ke-5 adalah membebaskan simpul bucket. Simpul-simpul pada bucket akan kita free satu persatu, mempersiapkan bucket untuk ronde selanjutnya.
contoh :
void freedata(struct tdata*a[]){
int i;
struct tdata *curr, *temp;
for(i=0;i<10;i++){
curr=a[i];
while(curr){
temp=curr;
curr=curr->next;
free(temp);
}
}
}
- Sehingga jika seluruh langkah dilakukan urutan pensortingan radix digambarkan sebagai berikut
Ronde-1
0 :150/
1 :81->441/
2 :312/
3 :[EMPTY]
4 :94/
5 :535->295/
6 :66/
7 :717->697/
8 :958->328/
9 :[EMPTY]
Ronde-2
0 :[EMPTY]
1 :411->312->717/
2 :328/
3 :535/
4 :[EMPTY]
5 :150->958/
6 :66/
7 :[EMPTY]
8 :51/
9 :94->295->697/
Ronde-3
0 :66->81->94/
1 :150/
2 :295/
3 :312->328/
4 :411/
5 :535/
6 :697/
7 :717/
8 :[EMPTY]
9 :958/
Sehingga hasilnya menjadi : 66,81,94,150,295,312,328,411,535,697,717,958.
Struktur Data 