Counting Sort
Counting sort merupakan sebuah teknik pengurutan dengan cara menghitung jumlah kemunculan dari setiap data yang berada di dalam array. Pada algorithma ini kita harus membuat sebuah array penampung untuk menyimpan jumlah kemunculan data dimana ukuran dari array tersebut harus sejumlah range angka yang bisa di input oleh user. Algorithma ini dapat mengurutkan data dari besar ke kecil (Ascending) dan kecil ke besar (Descending). Algoritma ini tidak cocok untuk set data dengan jumlah besar karena kompleksitas dari algorithma ini adalah Ο(n+r) di mana n adalah jumlah item dan r adalah jarak dari inputan.
Berikut gambaran dari implementasi Counting Sort:
Diketahui int arr[] = {5, 2, 3, 4, 1, 5, 6}. Misalkan kita hanya memiliki angka dengan range 0 – 10. Pertama-tama kita harus mempersiapkan sebuah array untuk untuk menyimpan jumlah data dalam array yang disebut int count[11] = {0}, maka akan membentuk array sebagai berikut:
| total | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1st Cycle:
(5, 2, 3, 4, 1, 5, 6) ->count[5]++;
| total | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
2nd Cycle:
(5, 2, 3, 4, 1, 5, 6) ->count[2]++;
| total | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
3rd Cycle:
(5, 2, 3, 4, 1, 5, 6) ->count[3]++;
| total | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
4th Cycle:
(5, 2, 3, 4, 1, 5, 6) ->count[4]++;
| total | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
5th Cycle:
(5, 2, 3, 4, 1, 5, 6) ->count[1]++;
| total | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
6th Cycle:
(5, 2, 3, 4, 1, 5, 6) ->count[5]++;
| total | 0 | 1 | 1 | 1 | 1 | 2 | 0 | 0 | 0 | 0 | 0 |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
7th Cycle:
(5, 2, 3, 4, 1, 5, 6) ->count[6]++;
| total | 0 | 1 | 1 | 1 | 1 | 2 | 1 | 0 | 0 | 0 | 0 |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Pada looping yang terakhir, kita sudah mendapatkan jumlah kemunculan dari setiap angka. Kita tinggal membuat sebuah looping untuk mengcheck apakah array untuk setiap nilai tersebut nilainya 0, jika tidak maka cetak angka data array tersebut.Output yang akan dihasilkan dari counting sort sebagi berikut: 1, 2, 3, 4, 5, 5, 6.
Berikut implementasi dari Counting Sort menggunakan Bahasa C:
|
#include <stdio.h>
int main() { int arr[]={5, 2, 3, 4, 1, 5, 6}; int n = sizeof(arr)/sizeof(int); int count[11];
for(int i=0;i<=10;i++){ //inisialisasinilaiawal count count[i]=0; }
for(int i=0;i<n;i++){ //counting sort count[arr[i]]++; }
for(int i=0;i<=10;i++){ while(count[i]!=0){ printf(“%d “,i); count[i]–; } }
return 0; } |
Reference:
https://www.geeksforgeeks.org/counting-sort/
Published at :