SortingPemulaFase 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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Array
·Konsep frekuensi

Real-World Uses

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

Complexity O(n + k)