Counting Sort

ANALISIS ALGORITMA PENGURUTAN NILAI

DENGAN MENCACAH (COUNTING SORT)

                                                                    

1.    Ide Dasar Counting Sort

Counting  Sort  adalah algoritma  pengurutan  efektif  dan  efisien  yang melakukan  pengurutan  dengan  ide  dasar  meletakkan elemen pada posisi yang benar, di mana penghitungan posisi  yang benar dilakukan dengan cara menghitung (counting)  elemen-elemen  dengan  nilai  lebih  kecil atau  sama  dengan  elemen  tersebut.

             Untuk dapat melakukan pengurutan dengan counting sort rentang nilai untuk kumpulan data yang akan diurutkan harus diketahui, katakanlah k.

            Ide dasar dari counting sort adalah menentukan, untuk setiap elemen x, jumlah elemen yang lebih kecil daripada x, yang kemudian informasi ini digunakan untuk menentukan posisi x. Contoh sederhanannya jika ada 6 elemen yang lebih kecil dari x, maka x akan mendapatkan posisi di posisi 7.               

     

2.    Implementasi Counting Sort

Pengurutan dengan pencacahan adalah pengurutan yang paling sederhana. Jika diketahui bahwa tabel yang akan diurutkan nilainya mempunyai daerah atau range tertentu dan merupakan bilangan bulat (integer) misalnya [1..k], maka cara paling sederhana untuk mengurutkan adalah:

1.    Sediakan tabel C[1..k] yang diinisialisasi dengan nol, yang pada akhir proses C[i] berisi banyaknya elemen asal T yang berharga i.

2.    Tabel asal T dibentuk kembali dengan menuliskan harga-harga yang ada dengan jumlah  sesuai dengan yang ada di C.

 

3.    Algoritma dan Kompleksitas Waktu Counting Sort

      Implementasi algoritma pengurutan dengan mencacah adalah sebagai berikut:

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 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;

 

     

Waktu yang dibutuhkan untuk mengurutkan data menggunakan counting sort bisa didapat dari perhitungan sebagai berikut :

Loop 1

       T(n) = k

Loop 2

       T(n) = n

Loop 3

       T(n) = k

Loop 4

       T(n) = n

Maka T(n)            = k + n +k +n

                       = 2k + 2n

Sehingga total waktu yang dibutuhkan adalah O(n)

4.    Analisis mengenai Counting Sort

Syarat agar pengurutan ini dapat dilakukan adalah diketahuinya rentang nilai data-datanya. Data-data yang akan diurutkan juga harus berupa bilangan bulat  (integer). Counting sort bisa efisien bila k tidak jauh lebih besar daripada n. Di mana semakin besar k maka memori tambahan yang diperlukan menjadi sangat besar. Contoh di mana counting sort dapat menjadi efisien adalah bila mengurutkan siswa-siswa dalam sebuah sekolah berdasar nilainya, dengan nilai adalah bilangan bulat dengan rentang 0..100. Dan contoh dimana counting sort akan sangat buruk kinerjanya adalah untuk data yang rentangnya sangat besar, misal dengan rentang 0..2³²-1.

Counting sort memiliki properti yang penting, yaitu ke-stable-an. Di mana data-data dengan nilai yang sama akan diurutkan berdasar urutan kemunculan pada array asal. Properti ini sangat penting dalam pengurutan data majemuk. Dengan kompleksitas O(n), metode pengurutan ini sangat cepat dan efektif. Yang diimbangi dengan kelemahan yaitu dibutuhkan memori tambahan sebagai array bantu dalam prosesnya.

Jika pengurutan dengan mencacah dijalankan pada element integer berukuran 32 bit, maka kasus terbaik terjadi berisi satu jenis element. Kasus terburuk terjadi ketika k_min bernilai -2³² dan k_max bernilai 2³². Loop 1 dan Loop 3 mempunyai O(k). Loop 2 dan Loop 4 mempunyai O(n). Sehingga dapat dijabarkan sebagai berikut:

      T(n)           =  O(k) + O(n) + O(k) + O(n)

                         =  O(k) + O(k) + O(n) + O(n)

                         =  O(k) + O(n)

                         =  O(k+n)

                         =  O(n)

Dengan contoh dan algoritma yang telah dibahas, jelas bahwa counting sort melakukan pengurutan tanpa melakukan perbandingan antar data.

5.    Kesimpulan 

Untuk melakukan pengurutan nilai ynag paling sederhana dan paling mudah dimengerti adalah algoritma counting sort namun algoritma ini tidak efektif digunakan pada tabel dengan range yang besar. Dimana semakin besar k, maka kebutuhan memori menjadi sangat besar. Secara  lebih  mendalam,  Counting  Sort  adalah algoritma  pengurutan  efektif  dan  efisien  yang melakukan  pengurutan  dengan  ide  dasar  meletakkan elemen pada posisi yang benar, di mana penghitungan posisi  yang benar dilakukan dengan cara menghitung (counting)  elemen-elemen  dengan  nilai  lebih  kecil atau  sama  dengan  elemen  tersebut.  Dan  memiliki kompleksitas waktu linier O(n).  Walaupun  tidak  dapat digunakan secara luas karena banyaknya batasan.

Daftar Pustaka :

Atrinawati, Lovinta. ANANLISIS KOMPLEKSITAS ALOGORITMA UNTUK BERBAGAI MACAM METODE PENCARIAN NILAI (SEARCHING) DAN PENGURUTAN NILAI (SORTING) PADA TABEL. ITB (Diakses tanggal 20 Oktober 2008)

Dominikus Damas Putranto. Pengkajian Algoritma Pengurutan-Tanpa-Pembandingan

Counting Sort dan Radix Sort. ITB (Diakses tanggal 20 Oktober 2008)

No Name. Counting Sort http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/countingSort/countingSort.html (Diakses tanggal 20 Oktober 2008)