Radix sort merupakan salah satu
algoritma yang mengklasifikasikan data sesuai dengan kategori terurut, dan
seterusnya sesuai kebutuhan, lalu subkategori-kategori tersebut digabungkan
kembali, dalam radix sort dimana dalam prosesnya tidak melakukan perbandingan
antar data, dan tiap kategori dilakukan pengklasifikasian lagi. Algoritma radix sort dapat direpresentasikan dalam berbagai cara,
terutama bagian bucket-nya. Bucket data dapat direpresentasikan
dalam bentuk array atau queue.
Berikut ini adalah contoh penggunaan
algoritma radix sort untuk pengurutan sebuah kumpulan bilangan bulat positif,
dengan jumlah digit maksimal 3 :
241 076 863 387 082 744 232 956 674
Pertama kali
data dibagi-bagi sesuai dengan digit terkanan (nilai satuan):
|
241
|
076
|
863
|
387
|
082
|
644
|
232
|
956
|
774
|
Kemudian dikategorikan Digit Isi
|
0
|
-
|
5
|
-
|
|
1
|
241
|
6
|
076, 956
|
|
2
|
082, 232
|
7
|
387
|
|
3
|
863
|
8
|
-
|
|
4
|
674, 744
|
9
|
-
|
Kemudian diurutkan kembali, dan dibagi-bagi sesuai
nilai tengah (nilai puluhan):
|
241
|
082
|
232
|
863
|
674
|
744
|
076
|
956
|
387
|
Kemudian dikategorikan Digit Isi
|
0
|
-
|
5
|
956
|
|
1
|
-
|
6
|
863
|
|
2
|
-
|
7
|
076, 674,
|
|
3
|
232
|
8
|
082, 387
|
|
4
|
241, 744
|
9
|
-
|
Kemudian diurutkan kembali, dan dibagi-bagi sesuai
nilai terkiri (nilai ratusan):
|
232
|
241
|
744
|
956
|
863
|
076
|
674
|
082
|
387
|
Kemudian dikategorikan Digit Isi
|
0
|
076, 082
|
5
|
-
|
|
1
|
-
|
6
|
674
|
|
2
|
232, 241
|
7
|
744
|
|
3
|
387
|
8
|
863
|
|
4
|
-
|
9
|
956
|
Kemudian dikategorikan Digit Isi
|
076
|
082
|
232
|
241
|
387
|
674
|
744
|
863
|
956
|
Maka data nilai sudah terurut. Berikut bentuk codingan
untuk Radix sort:
#include
<bits/stdc++.h>
using
namespace std;
void
gen_array(int *A){
cout << "Generated array
: \n";
for(int i = 0; i<10; i++){ //fungsi void gen_array untuk mentukan data yang habis dibagi
1000 dan disimpan ke array A
A[i] = rand()%1000;
cout << A[i]
<< " ";
}
cout << endl; //newline
}
void
radix_sort(int *A){
vector<int> ember[10]; //fungsi untuk
menyediakan tempat untuk mengelompokan data
int maks = 0, derajat = 1; //derajat 1= satuan
for(int i = 0; i < 10; i++)
if(maks < A[i]) maks
= A[i]; //fungsi untuk mencari nilai maksimal dari data
while((maks/derajat)
> 0) //looping akan terus berulang sampai pembagian
maks/derajat hasilnya 0, sehingga looping akan berhenti ketika melebihi data
maksimal
{
for(int i = 0; i <
10; i++)
{
ember[A[i]/derajat
% 10].push_back(A[i]); //fungsi untuk mengelompokan
angka terakhir pada bilangan di array A dan dimasukan ke dalam tempat yang sudah
disediakan/embernya.
}
int counter = 0;
for(int i = 0; i <
10; i++)
{
if(!ember[i].empty()) //program akan berjalan jika ember tidak kosong
{
for(int
j = 0; j < ember[i].size(); j++) //looping sampai
banyaknya data dalam indeks ember
{
A[counter]
= ember[i][j]; //data dalam ember, disimpan ke array.
Ex: buat ember baru untuk menampung
nilai awal untuk j=0 dan i=1 maka yang diambil dimasukkan maka akan jadi nilai
yang terurut
counter++;
//counter
bertambah sehingga nilai j dan i juga akan bertambah
}
}
}
for(int i = 0; i <
10; i++)
ember[i].clear();
//semua data
dimasukan ke array A, array ember kosong
derajat*=10; //setelah perulangan
data terakhir selesai, derajat dikali untuk mengelompokan nilai tengah, begitu
seterusnya sampai angka pertama selesai dikelompokkan ke array A
}
}
int
main(){
int *A = (int*) malloc(10 *
sizeof(int)); //menyediakan 10 tempat untuk data yang
akan diurutkan
gen_array(A); //memanggil fungsi
radix_sort(A);
cout << "\nHasil
sorting\n";
for(int i = 0; i < 10 ; i++)
cout <<
"indeks ke-" << i << " : " << A[i]
<< endl; //menampilkan data yang sudah terurut
return 0;
}
