Algoritma Counting Sort

   Algoritma Counting Sort

Counting Sort adalah algoritma pengurutan efektif dan efisien yang melakukan pengurutan dengan ide dasar meletakkan elemen pada posisi yang benar, dimana penghitungan posisi yang benar dilakukan dengan cara menghitung (counting) elemen-elemen dengan nilai lebih kecil atau sama dengan elemen tersebut. Contoh sederhana saja jika terdapat 12 elemen yang lebih kecil daripada x, maka x akan mendapatkan posisinya di posisi 13.

Tentu saja, sedikit modifikasi harus dilakukan agar metode ini dapat menangani kasus di mana terdapat elemen elemen lain yang nilainya sama dengan x. Dimana tentu saja kita tidak dapat menempatkan semua elemen yang nilainya sama dengan x di posisi yang sama.

Keungggulan Algoritma Counting Sort

Keunggulan dari algoritma counting sort adalah dapat mengurutkan dengan waktu yang lebih singkat, karena tidak membandingkan dengan elemen lain.

Kelemahan Algoritma Counting Sort

Kelemahan algoritma counting sort adalah menggunakan array yang terlalu banyak.

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.

 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.

procedure CountingSortDesc(var TabI: TblInt);
var iLoop1,iLoop2,k : integer;
min,max : integer;
tbCount : array of integer;
begin
{
Inisialisasi array
}
min := TabI.Data[IndexMin(TabI)];
max := TabI.Data[IndexMax(TabI)];
setlength(tbCount, max+1 – min) ;
for iLoop1 := 0 to (max-min) do
tbCount[iLoop1] := 0;
for iLoop1 := IMin to TabI.Neff  do
tbCount[ TabI.Data[iLoop1] – min ] := tbCount[ TabI.Data[iLoop1] – min ] + 1;
iLoop2 := TabI.Neff+1;
for iLoop1 := 0 to (max+1-min) do
begin
if(tbCount[iLoop1] <> 0) then
for k := 1 to tbCount[iLoop1] do
begin
iLoop2 := iLoop2 – 1;
TabI.Data[iLoop2] := iLoop1+min;
end;
end;
end;