Makalah Redix Sort | Struktur Data (Sorting)

BAB I

PENDAHULUAN

1.1.Latar Belakang

Dalam makalah ini akan dibahas bagaimana cara pengurutan data dengan menggunakan metode redix sort. Mengetahui cara pengurutan data dengan metode redix sort sangat penting karena ini bagian dari Mata Kuliah Struktur Data.

1.2.Rumusan Masalah

a) Apa itu Redix Sort?

b) Algoritma redix sort

c) Bagaimana aplikasi programnya?

d) Kelebihan dan kekurangan.

1.3.Tujuan Masalah

a) Agar mengetahui apa itu metode pengurutan redix sort.

b) Agar mengetahui algoritma dari redix sort.

c) Mahasiswa bias mengurutkan data dengan aplikasi program yang diberikan.

d) Mengetahui kelebihan dan kekurangan dari metode pengurutan Redix Sort.

BAB II

PEMBAHASAN

2.1. Pengertian Radix Short

Radix Sort merupakan salah satu algoritma Non-Comparasion Sort (pengurutan tanpa perbandingan). Proses yang dilakukan dalam metode ini adalah mengklasifikasikan/menyelesaikan data sesuai dengan kategori terurut yang tertentu, dan tiap kategori dilakukan pengklasifikasian lagi, dan seterusnya sesuai kebutuhan, kemudian subkategori-kategori atau bagian-bagian dari kategori tersebut digabungkan kembali.

Secara harfiah Radix dapat diartikan sebagai posisi dalam angka, karena cara ini pertama kalinya mengurutkan nilai-nilai yang dimasukan (input) berdasarkan radix pertamanya, lalu pengurutan dilakukan berdasarkan radix keduanya, dan begitu seterusnya. Pada sistem desimal, radix adalah digit dalam angka desimal. Misalnya, angka “169” mempunyai 3 digit yaitu 1,6 dan 9.

2.2. Algoritma Radix Short

Algoritma radix sort adalah salah satu algoritma pengurutan yang paling mangkus karena tidak menggunakan perbandingan secara langsung. Untuk kasus bilangan bulat (integer), algoritma ini akan mengurutkan data dengan mengelompokkan data-data berdasarkan digit yang memiliki significant position dan value yang sama. Kelompok digit ini ditampung dalam suatu variable “bucket”. Struktur datanya direpresentasikan dengan array. Algoritma ini pertama kali diperkenalkan pada tahun 1887 oleh Herman Hollerith pada mesin tabulasi.

Ada dua jenis radix sort saat ini :

- LSD (least significant digit) radix sort, yaitu radix sort yang mengurutkan data dimulai dari digit terkecil. Algoritma ini cenderung stabil karena tetap mengikuti urutan awal data-data sebelum diurutkan.

- MSD (most significant digit) radix sort, yaitu radix sort yang mengurutkan data dimulai dari digit terbesar. Algoritma ini lebih susah untuk direalisasikan daripada LSD radix sort, dan biasanya tidak mengikuti urutan awal data-data yang akan diurutkan.

Makalah ini hanya akan membahas LSD radix sort.

Misalkan terdapat sebuah array dengan elemen “121 76 823 367 232 434 742 936 274”. Dengan menggunakan algoritma radix short :

Pertama kali data dibagi-bagi sesuai dengan digit terkanan :

121

823

367

232

434

742

936

274

Pada saat penentuan kategori lihat terlebih dahulu nilai digit yang terbesar dicontoh ini yakni nilai digit yang terbesar 9 sehingga kategori sebanyak 9 baris dan diawali dari 0. Langsung aja supaya lebih jelas perhatikan tabel dibawah ini :

Kategori Digit 1 (satuan)	Isi
0	-
1	121
2	232, 742
3	823
4	434, 274
5	-
6	76, 936
7	367
8	-
9	-

Hasil pengkategori pertama kemudian digabungkan kembali menurut penjelasan yang diatas:

121

232

742

823

434

274

936

367

Kemudian dilakukan pengkategorian kembali berdasarkan digit yang kedua dengan berpatokan(melihat) baris urutan pengkategorian pertama yaitu :

Kategori Digit 2 (puluhan)	Isi
0	-
1	-
2	121, 823
3	232, 434, 936
4	742
5	-
6	367
7	274, 76
8	-
9	-

Selanjutnya hasil pengkategori kedua digabungkan kembali.

121

823

232

434

936

742

367

274

Kemudian langkah ketiga (terakhir), dilakukan pengkategorian kembali berdasar digit ketiga. dengan berpatokan (melihat) baris urutan pengkategorian kedua yaitu :

Kategori Digit 3 (Ratusan)	Isi
0	076
1	121
2	232, 274
3	367
4	434
5	-
6	-
7	742
8	823
9	936

Jadi, hasil akhirnya dapat dituliskan :

121

232

274

367

434

742

823

936

Dari langkah-langkah yang telah dilakukan dalam proses pengurutan menggunakan radix sort, jelas tampak bahwa radix sort termasuk algoritma pengurutan tanpa pembanding. Dengan sifatnya yang melihat digit-digit angka sebagai pengontrolnya, Radix Sort dapat diimplementasikan dalam pengurutan bilangan desimal dan bilangan bit. Namun dalam penggunaannya radix sort bisa dimodifikasi sehingga bisa digunakan untuk menggurutkan data data negatif dan pecahan.

2.3. Kelebihan dan Kekurangan Redix Short

Algoritma radix sort memiliki kelebihan dan kekurangan yang berbeda dibandingkan dengan algoritma pengurutan yang lain. Beberapa kelebihan algoritma radix sort adalah sebagai berikut :

- Algoritma sangat mangkus. Hal ini dapat dilihat dari kompleksitas waktu asimptotiknya yang sangat kecil (O(kN)). Hal ini mengakibatkan algoritma radix sort sangat efektif untuk data dalam jumlah yang sangat besar sekalipun.

- Konsep algoritma mudah dipahami. Algoritma radix sort mengurutkan data berdasarkan digit, tidak melalui proses perbandingan yang cenderung sulit dipahami.

Walaupun memiliki banyak kelebihan dibandingkan algoritma pengurutan yang lain, algoritma ini memiliki kekurangan : realisasi program rumit dan kurang fleksibel untuk digunakan pada tipe data lain.

Realisasi program untuk algoritma radix sort tidak semudah memahami konsep dasarnya. Secara umum, algoritma ini membutuhkan bucket untuk mengelompokkan data-data yang sedang diurutkan. Inisialisasi bucket untuk kasus ini tidak mudah dilakukan. Pada awalnya, radix sort hanya dapat digunakan untuk data bertipe bit dan desimal. Tetapi, seiring waktu, radix sort mulai dikembangkan untuk tipe data yang lain. Saat ini radix sort sudah dapat digunakan untuk tipe data berupa bilangan pecahan dan bilangan negatif. Akan tetapi, modifikasi terhadap algoritma ini menjadi signifikan. Pada umumnya, pengembangan algoritma radix sort untuk tipe data lain dibantu dengan menggunakan counting sort, yang merupakan salah satu algoritma pengurutan yang tidak menggunakan perbandingan. Penulis tidak akan membahas algoritma ini mengingat batasan makalah yang diberikan.

2.4. Program Redix Short dalam Bahasa C++

Realisasi radix sort di C dapat dilihat pada Script di bawah ini :

//program C++ Redix Short

#include <stdio.h>

#define MAX 20

#define SHOWPASS

#define BASE 10

void print(int *a, int n)

{

int i;

for (i = 0; i < n; i++)

printf("%d\t", a[i]);

}

void radixsort(int *a, int n)

{

int i, b[MAX], m = a[0], exp = 1;

//Get the greatest value in the array a and assign it to m

for (i = 1; i < n; i++)

{

if (a[i] > m)

m = a[i];

}

//Loop until exp is bigger than the largest number

while (m / exp > 0)

{

int bucket[BASE] = { 0 };

//Count the number of keys that will go into each bucket

for (i = 0; i < n; i++)

bucket[(a[i] / exp) % BASE]++;

//Add the count of the previous buckets to acquire the indexes after the end of each bucket location in the array

for (i = 1; i < BASE; i++)

bucket[i] += bucket[i - 1]; //similar to count sort algorithm i.e. c[i]=c[i]+c[i-1];

//Starting at the end of the list, get the index corresponding to the a[i]'s key, decrement it, and use it to place a[i] into array b.

for (i = n - 1; i >= 0; i--)

b[--bucket[(a[i] / exp) % BASE]] = a[i];

//Copy array b to array a

for (i = 0; i < n; i++)

a[i] = b[i];

//Multiply exp by the BASE to get the next group of keys

exp *= BASE;

#ifdef SHOWPASS

printf("\nPASS : ");

print(a, n);

#endif

}

int main()

{

int arr[MAX];

int i, n;

printf("Enter total elements (n <= %d) : ", MAX);

scanf("%d", &n);

n = n < MAX ? n : MAX;

printf("Enter %d Elements : ", n);

for (i = 0; i < n; i++)

scanf("%d", &arr[i]);

printf("\nARRAY : ");

print(&arr[0], n);

radixsort(&arr[0], n);

printf("\nSORTED : ");

print(&arr[0], n);

printf("\n");

return 0;

}

Outputnya sebagai berikut :

BAB III

KESIMPULAN

Algoritma radix sort melakukan pengurutan terhadap data berdasarkan digit (radix) dari data-data yang sedang diproses.

Algoritma radix sort adalah salah satu algoritma tanpa perbandingan yang mangkus dan sederhana untuk dipahami, tetapi rumit dalam realisasinya.

Algoritma radix sort dapat direpresentasikan dalam berbagai cara, terutama bagian bucket-nya. Bucket data dapat direpresentasikan dalam bentuk array atau queue.

Algoritma radix sort dapat digunakan untuk tipe data selain bit dan desimal, tetapi diperlukan bantuan algoritma pengurutan lain, seperti counting sort.

GALAKSI3

Makalah Redix Sort | Struktur Data (Sorting)

Artikel terkait :

2comments :