Program komputer merupakan instruksi-instruksi logis yang tertulis dalam sebuah source code yang dibaca oleh komputer dan selanjutnya dieksekusi. Salah satu masalah yang dapat diselesaikan oleh komputer adalah pengurutan data. Baik pengurutan data dari yang terbesar ke yang terkecil ataupun sebaliknya.
Di antara banyak algoritma pengurutan tersebut terdapat satu kategori algoritma pengurutan yang dalam prosesnya tidak melakukan pembandingan antar data. Yang sering disebut Non-Comparison Sorting Algorithm, atau dalam bahasa IndonesiaAlgoritma Pengurutan-Tanpa-Pembandingan.
Tulisan ini akan mencoba membahas salah satu teknik sorting yang tanpa melakukan perbandingan data. Ada dua teknik algoritma untuk melakukan sorting tanpa membandingkan data yaitu : Counting Sort dan Radix Sort. Dalam tulisan ini akan dibahas teknik Counting Sort.
Secara umum yang proses yang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu, dan dalam tiap kategori dilakukan pengklasifikasian lagi, dan seterusnya sesuai dengan kebutuhan, kemudian subkategori-subkategori tersebut digabungkan kembali, yang secara dilakukan hanya dengan metode sederhana concatenation. Ide dasar dari counting sort adalah menentukan, untuk setiap elemen x jumlah yang lebih kecil dari x setelah itu informasi ini digunakan untuk menentukan1 posisi x. Contoh sederhana misalkan terdapat 6 elemen yang lebih kecil dari x maka x menjadi posisi ke 7.
Berikut merupakan algoritma counting sort :
algorithm counting_sort (A,k)
Input : A : array [1..n] of integer, k: max (A)
Output : B : array [1..n] of integer
for i = 1 to k do
C[i] = 0
for j = 1 to length(A) do
C[A[j]] = C[A[j]] + 1
for 2 = 1 to k do
C[i] = C[i] + C[i-1]
for j = 1 to length(A) do
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1
Setelah dilakukan implementasi algoritma tersebut ke dalam program, dalam hal ini menggunakan JavaScript, berikut merupakan script programnya.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | <script type = "text/javascript"> function countingSort(A) { B=[];C=[]; var max = A[0]; for(i=0;i<A.length;i++) { if(max<A[i]) max=A[i]; } //counting for (i=0;i<=max;i++) { C[i]=0; } for (i=0;i<A.length;i++) { C[A[i]]++; } for (i=1;i<=max;i++) { C[i]=C[i]+C[i-1]; } for (i=A.length;i>=0;i--) { B[C[A[i]]]=A[i]; C[A[i]]=C[A[i]]-1; } return B; } //test data=[3,4,6,3,6,8,3,5,8,4,2,6,9,5,3,4,6]; document.write("before : "); for (i=0;i<data.length;i++) { document.write(data[i]+" "); } document.write(" "); document.write("after : "); data=countingSort(data); for (i=1;i<data.length;i++) { document.write(data[i]+" "); } script> |
Dari data random pada array data=[3,4,6,3,6,8,3,5,8,4,2,6,9,5,3,4,6];
setelah program terebut dijalankan maka data itu menjadi terurut yang dapat terlihat pada gambar dibawah :
setelah program terebut dijalankan maka data itu menjadi terurut yang dapat terlihat pada gambar dibawah :
Dengan demikian data yang semula teracak setelah program itu dijalankan maka data akan terurut seperti pada gambar diatas. Namun kekurangan dari algortima ini adalah tidak bisa mengurutkan data string dan data bilangan desimal.
Referensi :
Pengkajian Algoritma Tanpa Perbandingan Counting Sort dan Radix Sort. Oleh : Dominnikus Damas Putranto (Program Studi Teknik Informatika ITB).
0 komentar:
Posting Komentar