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.

Procedure CountingSort (Input/output T:array [1..N] of integer)
{Mengurutkan Tabel T integer [1..N] dengan pencacahan, dimana range atau rentang nilainya [1..k] dengan hasil akhir T terurut menaik , dengan asumsi:Nilai N (jumlah elemen T) dan k diketahui 
Asumsi : Nilai N (jumlah elemen T) dan k diketahui, rentang nilai untuk elemen T integer antara 1..k }

Kamus 
C : array [1..k] of integer {Tabel array pencacahan}
i, j : Integer {indek perulangan}
c : Integer {jumlah elemen T yang sudah diisi pada pembentukan kembali}

Algoritma 
for i = 1 to k do {Loop 1}
C[ i ] <-- 0;
endfor

for i = 1 to N do {Loop 2}
C[ T[ i ] ] <-- C[ T [ i ] ] + 1
endfor

C <-- 0

for i = 1 to k do {Loop 3}
if C[ i ] < > 0 then 
for j = 1 to C[ i ] do {Loop 4}
C <-- C + 1
T[C] <-- i
endfor;
endif;
endfor;

Sumber :

dewin221106.blogspot.com

Related Posts