Algorithme Sorting Radix Sort dan Codingan C++

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;

}