DUNIA ILMU: Algoritma Counting Sort (Pengurutan Data Tanpa Perbandingan)

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
        return B

Setelah dilakukan implementasi algoritma tersebut ke dalam program, dalam hal ini menggunakan JavaScript, berikut merupakan script programnya.

<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 : <br>");
for (i=0;i<data.length;i++) {
 document.write(data[i]+" ");
}
document.write("<br>");
document.write("after : <br>");
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 :

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).
http://en.wikipedia.org/wiki/Counting_sort
Some Sorting Algorithm (Course Material Computer Science UGM). Oleh : Azhari, Drs. MT. Dr. (Magister Ilmu Komputer UGM)
http://users.cs.cf.ac.uk/C.L.Mumford/tristan/CountPage.html

DUNIA ILMU

Pages

Kamis, 30 Juni 2011

Algoritma Counting Sort (Pengurutan Data Tanpa Perbandingan)

Tidak ada komentar:

Posting Komentar