PengurutanPemulaFase C–FE1E5

Counting Sort

Counting Sort mengurutkan tanpa membandingkan elemen: hitung berapa kali tiap nilai muncul ke dalam bucket, lalu keluarkan nilai sesuai hitungannya secara berurutan. Sangat cepat O(n+k) bila rentang nilai kecil.

Contoh kasus

Mengurutkan nilai ujian 0-100 ribuan siswa: cukup hitung frekuensi tiap nilai lalu tuliskan berurutan.

Silabus

Mengurutkan tanpa membandingkan elemen, cukup menghitung frekuensi tiap nilai lalu menuliskannya kembali secara berurutan.

Tujuan Belajar

·Memahami pengurutan berbasis hitungan, bukan perbandingan
·Menjelaskan kapan Counting Sort lebih cepat dari sorting biasa
·Menerapkan bucket frekuensi untuk rentang nilai yang kecil

Cara Kerja

·Siapkan bucket hitungan untuk tiap nilai yang mungkin
·Telusuri data, tambah hitungan pada bucket nilainya
·Baca bucket dari nilai terkecil ke terbesar
·Tuliskan tiap nilai sebanyak hitungannya
·Hasilnya array terurut tanpa satu pun perbandingan

Prasyarat

·Array
·Konsep frekuensi

Contoh Nyata

·Menyusun nilai ujian 0-100 dari ribuan siswa sekelas
·Menghitung dan merapikan umur peserta lomba yang seragam rentangnya

Kompleksitas O(n + k)