ALGORITMA COUNTING SORT
A. Definisi atau Pengertian Algoritma Counting
Sort
Definisi atau pengertian counting sort secara etimologis (tata bahasa) berasal dari dua kata
dalam bahasa Inggris, yaitu counting
yang berarti menghitung atau mencacah dan sort
yang berarti menyortir atau bisa diartikan menyusun. Sedangkan secara
terminologis dalam dunia pemrograman, counting
sort adalah sebuah teknik algoritma dalam mengurutkan data dari yang
terkecil ke terbesar (ascending) atau
dari yang terbesar ke terkecil (descending)
dimana dalam proses pengurutan tersebut tidak ada tahapan pembandingan data.
Oleh karena itu, counting sort
dimasukkan ke dalam kategori non-Comparison
Sort atau dalam bahasa
Indonesia-nya Pengurutan tanpa-Pembandingan.
Dalam prosesnya, teknik algoritma counting sort melibatkan pencacahan atau perhitungan bilangan data
dan indeks array. Perhitungan tersebut
mencakup penjumlahan dan pengurangan. Oleh karena itu, teknik algortima sorting ini dinamakan dengan counting sort. Algoritma ini diciptakan oleh Harold H. Seward pada tahun 1954.
B. Teori Algoritma Counting Sort
Pengurutan (sorting) adalah proses mengatur atau menyusun sekumpulan objek-
bisa berupa bilangan, huruf, kata, ataupun data-menurut urutan atau susunan
tertentu, yaitu bisa dari yang terkecil ke terbesar (ascending)
atau dari yang terbesar ke terkecil (descending).
Secara garis besar, teknik
algoritma sorting diklasifikasi
menjadi 2, yaitu pengurutan dengan pembandingan (comparison sort), seperti selection
sort, bubble sort, dan insertion sort, dan pengurutan tanpa pembandingan (non comparison sort).
Counting sort merupakan
salah satu teknik algoritma yang bisa digunakan untuk mengurutkan atau menyusun
data bilangan integer (bilangan
bulat) dimana dalam proses pengurutan tersebut tidak ada tahapan pembandingan
data (non-comparison sort).
Berdasarkan beberapa artikel, terciptanya
algoritma counting sort terinspirasi
atau diilhami oleh prinsip PigeonHole
(prinsip rumah merpati) dalam bidang matematika yang dicetuskan oleh ahli
matematika dari Jerman yang bernama Johann
Peter Gustav Lejeune Dirichlet pada tahun 1834.
Prinsip PigeonHole yang dikemukakan oleh penemunya terbagi ke dalam
beberapa bentuk, namun menurut kami yang menjadi inspirasi algoritma counting sort adalah bentuk pertama,
yaitu : Jika (k + 1) atau lebih obyek
ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang
memuat dua atau lebih obyek tersebut.
Misalkan, jika n merpati
ditempatkan pada m rumah merpati dimana n > m maka terdapat rumah merpati
yang memuat paling sedikit dua merpati.
Contoh 1: Jika terdapat 11
pemain dalam sebuah tim sepakbola yang menang dengan angka 12-0, maka haruslah
terdapat paling sedikit satu pemain dalam tim yang membuat gol paling sedikit
dua kali.
Contoh 2: Jika kita menghadiri 6
kuliah dalam selang waktu Senin sampai Jumat, maka haruslah terdapat paling
sedikit satu hari ketika kita menghadiri paling sedikit dua kelas.
Jika diterapkan ke dalam masalah
pengurutan, bila terdapat array dengan rentang nilai 1 . . 10 menempati 12
elemen maka akan terdapat bilangan yang sama dalam array tersebut. Bagaimana
jelasnya hubungan antara prinsip PigeonHole
dengan algoritma Counting Sort perlu
pengkajian yang mendalam. Pada intinya kami sampaikan bahwa berdasarkan sumber
bacaan, teknik algoritma sorting yang
didalamnya tidak ada proses pembandingan data (non comparison sort), salah satunya adalah counting sort, terinspirasi oleh prinsip PigeonHole.
Algoritma counting sort digunakan untuk mengurutkan bilangan bulat dengan
range kecil yang tersimpan dalam sebuah array. Misal array data yang akan
diurutkan adalah A dengan jumlah data sebanyak n. Counting sort membutuhkan sebuah array C berukuran k yang bersifat
sementara untuk membantu dalam pencacahan sehingga penempatan bilangan sesuai
dengan urutan tertentu. Setiap elemen C[i] merepresentasikan jumlah elemen
dalam A yang nilainya adalah i. Kemudian dibutuhkan pula array B berukuran sama
dengan array A, dimana array B ini akan digunakan untuk menampung bilangan yang
sudah terurut atau tersusun. Gambarannya adalah sebagai berikut.
A → C → B
data asal
temporary data terurut
Pengulangan (looping) terjadi sebanyak empat tahapan,
yaitu tahapan pertama untuk menginisialisasi nilai elemen array C, tahap kedua
dan ketiga untuk mencacah elemen array C yang sudah terinisialisasi pada tahap
pertama, dan tahap keempat adalah memasukkan nilai ke setiap elemen array B sesuai
dengan urutan tertentu.
Syarat agar teknik pengurutan
ini dapat dilakukan adalah diketahuinya rentang nilai data yang terdapat pada
array asal. Data-data yang akan diurutkan juga harus berupa bilangan bulat (integer). Counting sort bisa efisien bila k tidak jauh lebih besar daripada n
karena semakin besar k maka memori tambahan yang diperlukan menjadi sangat
besar. Contoh dimana counting sort
dapat menjadi efisien adalah bila mengurutkan data beberapa siswa dalam sebuah sekolah
berdasar nilai dimana nilai untuk setiap siswa adalah bilangan bulat dengan
rentang 0 . . . 100. Sedangkan contoh dimana counting sort akan sangat buruk kinerjanya adalah untuk data bilangan
bulat yang rentangnya sangat besar, misal dengan rentang 0 . . 1000000.
Waktu yang dibutuhkan untuk
mengurutkan data dengan menggunakan algoritma counting sort bisa didapatkan dari perhitungan sebagai berikut :
Looping pertama membutuhkan
waktu O(k),
Looping kedua membutuhkan waktu
O(n),
Looping ketiga membutuhkan waktu
O(k), dan
Looping
keempat membutuhkan waktu O(n).
Jadi secara total membutuhkan
waktu O(k+n) yang seringkali dianggap k = O(n),
sehingga waktu total yang dibutuhkan menjadi O(n).
Keungggulan algoritma
counting sort adalah dapat
mengurutkan beberapa bilangan bulat (integer)
dengan waktu yang lebih singkat karena tidak adanya proses pembandingan
bilangan. Sedangkan kelemahan algoritma counting
sort adalah menggunakan array yang terlalu banyak bila range bilangan sangat berjauhan sehingga akan menghabiskan memori
yang cukup banyak.
Tidak ada komentar:
Posting Komentar