My first Magazine pemrograman-kompetitif-dasar | Page 46

3 Pencarian dan Pengurutan
1 1 2 2 3
1 2 3
5
4
5
Gambar 3.20: Tahap 9: Keluarkan isi dari setiap ember, mulai dari ember paling kiri.
1
1
2
2
3
5
Gambar 3.21: Tahap 10: Pengurutan selesai.
Implementasi Counting Sort
Ide ini dapat diwujudkan dengan menyiapkan tabel frekuensi yang berperan sebagai ”ember”.
Untuk setiap nilai elemen yang mungkin, catat frekuensi kemunculannya. Terakhir, iterasi tabel
frekuensi dari elemen terkecil sampai elemen terbesar. Tabel frekuensi dapat diimplementasikan
dengan array sederhana. Contoh implementasi Counting Sort dapat dilihat pada Algoritma 15
Contoh Kode
Algoritma 15 Algoritma counting sort .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
procedure C OUNTING S ORT (h)
. Catat frekuensinya
for i ← 1, N do
x ← h[i]
f table[x] ← f table[x] + 1
end for
. Tuang kembali ke h[]
index ← 1
for i ← 1, 100000 do
for j ← 1, f table[i] do
h[index] ← i
index ← index + 1
end for
end for
end procedure
Dapat diperhatikan bahwa kompleksitas counting sort adalah O(N + M), dengan M adalah
rentang nilai data. Jika M tidak terlalu besar, maka counting sort dapat bekerja dengan sangat
cepat. Lebih tepatnya, counting sort merupakan opsi yang sangat baik jika datanya memiliki
rentang yang kecil, misalnya data tentang usia penduduk yang rentangnya hanya [0, 125].
Bandingkan dengan algoritma pengurutan lain yang kompleksitasnya O(N 2 )!
36