Counting sort

Counting sort sama sekali tidak mengurutkan dengan membandingkan nilai. Jika Anda tahu setiap nilai adalah bilangan bulat antara, misalnya, 1 dan 40, Anda cukup menghitung berapa banyak masing-masing, lalu dari hitungan itu menentukan di mana tempat setiap nilai. Untuk rentang kecil, itu hampir secepat mungkin.

Batang-batang sebuah daftar, strip penghitung yang menunjukkan berapa kali setiap nilai muncul, dan baris buffer tempat setiap nilai punya bloknya sendiri
Batang-batang sebuah daftar, strip penghitung yang menunjukkan berapa kali setiap nilai muncul, dan baris buffer tempat setiap nilai punya bloknya sendiri

Hitung

Temukan nilai terkecil dan terbesar, lalu buat satu penghitung untuk setiap nilai di antaranya, semuanya mulai dari nol. Baca daftar sekali dari awal sampai akhir dan tambahkan satu ke penghitung setiap nilai yang Anda lihat. Kini penghitung membentuk histogram: berapa banyak angka 1, berapa banyak angka 2, dan seterusnya. Dengan n nilai dan k penghitung, ini butuh n langkah.

Jumlahkan

Nilai yang sama dengan nilai terkecil datang lebih dulu, jadi bloknya dimulai di tempat 1. Blok nilai berikutnya dimulai tepat setelahnya, dan seterusnya: setiap blok dimulai setelah jumlah semua hitungan sebelumnya. Total berjalan ini, yang disebut jumlah prefiks, mengubah histogram menjadi peta daftar yang terurut. Ini butuh k langkah.

Tempatkan

Baca daftar untuk kedua kalinya dan pindahkan setiap nilai ke tempat kosong berikutnya di bloknya. Karena nilai dipindahkan sesuai urutan kemunculannya, nilai yang sama tetap dalam urutan aslinya: counting sort stabil. Salin buffer kembali, dan daftar sudah terurut. Aplikasi menunjukkan setiap penghitung berkurang lagi saat nilainya ditempatkan.

Contoh

Ambil 4, 1, 3, 4, 2, 1, 4. Penghitung untuk 1 sampai 4 berakhir di 2, 1, 1, dan 3. Menjumlahkannya memberi blok-bloknya: angka 1 di tempat 1 dan 2, angka 2 di tempat 3, angka 3 di tempat 4, dan angka 4 di tempat 5 sampai 7. Menempatkan nilai sesuai urutan daftar menghasilkan 1, 1, 2, 3, 4, 4, 4: 7 nilai dihitung, 14 pemindahan, 4 penghitung, dan tanpa perbandingan.

Kapan memakainya

Total kerjanya tumbuh sebanding n + k. Jika k kecil dibandingkan n, seperti seribu skor ujian dari 0 sampai 100, counting sort lebih cepat daripada pengurutan berbasis perbandingan mana pun, yang butuh sekitar n log₂ n perbandingan. Jika rentangnya lebar, ia boros: beberapa nilai yang tersebar sampai sejuta butuh sejuta penghitung. Radix sort mengatasinya dengan menjalankan counting sort sekali per digit, sehingga setiap putaran hanya butuh sepuluh penghitung. Harold Seward menjelaskan counting sort, bersama radix sort, pada tahun 1954.

Jelajahi

Buka aplikasi dan tekan Langkah. Strip di antara daftar dan baris buffer menampilkan satu penghitung per nilai. Lihat penghitung terisi saat daftar dibaca, blok-blok muncul di buffer saat hitungan dijumlahkan, dan penghitung berkurang lagi saat nilai ditempatkan. Pilih sedikit nilai unik untuk melihat blok besar, atau ketik angka yang berjauhan untuk melihat berapa banyak penghitung yang dibutuhkan rentang lebar.

Pertanyaan yang sering diajukan

Berapa kompleksitas waktu counting sort?

O(n + k) untuk n nilai dan k nilai yang mungkin, serta memori tambahan O(n + k) untuk penghitung dan buffer.

Mengapa counting sort tidak selalu yang tercepat?

Karena biayanya bergantung pada rentang nilai, bukan hanya pada banyaknya nilai. Jika rentangnya jauh lebih besar daripada daftarnya, sebagian besar penghitung tetap nol dan waktu serta memori terbuang.

Bisakah counting sort menangani bilangan negatif?

Bisa. Penghitung berjalan dari nilai terkecil sampai terbesar, jadi kurangi dengan nilai terkecil untuk mendapat indeks penghitung. Aplikasi ini melakukan hal yang sama.

Apakah counting sort stabil?

Ya, selama nilai dipindahkan sesuai urutan daftar ke tempat kosong berikutnya di bloknya. Radix sort bergantung pada hal itu.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba counting sort