- Sedang dihitung
- Baru dipindah
- Di tempatnya
Counting sort
Counting sort bekerja jika nilainya bilangan bulat dalam rentang kecil. Ia menyiapkan satu penghitung untuk setiap nilai yang mungkin, menghitung berapa kali masing-masing muncul, dan dari hitungan itu tahu persis di mana tempat setiap nilai. Lihat penghitung terisi saat daftar dibaca, lalu kosong lagi saat setiap nilai pindah ke bloknya, satu pemindahan setiap kali. Tekan Putar untuk melihat pengurutan, atau Langkah dan Mundur untuk maju satu pemindahan setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Strip di antara daftar dan baris buffer berisi satu penghitung untuk setiap nilai. Kotak-kotak menghitung nilai yang dihitung, pemindahan, dan penghitung. Pilih jumlah batang, urutan awalnya, atau ketik angka sendiri. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Pilih jumlah batang dan urutan awalnya, atau ketik bilangan bulat sendiri. Coba daftar dengan sedikit nilai unik.
- Tekan Putar, atau gunakan Langkah dan Mundur untuk memindahkan satu nilai setiap kali. Geser penggeser langkah untuk melompat ke mana saja dalam pengurutan.
- Amati penghitungnya: terisi saat daftar dibaca, lalu berkurang saat setiap nilai ditempatkan.
Cara kerja counting sort
Buat penghitung untuk setiap nilai dari yang terkecil sampai yang terbesar. Baca daftar sekali dan tambahkan satu ke penghitung setiap nilai yang Anda lihat. Lalu jumlahkan hitungannya mulai dari nilai terkecil: blok suatu nilai dimulai tepat setelah semua nilai yang lebih kecil. Terakhir, telusuri daftar sekali lagi dan pindahkan setiap nilai ke tempat kosong berikutnya di bloknya, lalu salin hasilnya kembali.
Cepat untuk rentang kecil
Counting sort membaca daftar dua kali dan menelusuri penghitung sekali, jadi kerjanya tumbuh sebanding n + k: jumlah nilai ditambah jumlah penghitung. Untuk banyak nilai dalam rentang kecil, seperti skor ujian dari 0 sampai 100 atau usia, ia mengalahkan pengurutan berbasis perbandingan mana pun. Untuk rentang lebar, ia membuang waktu dan memori untuk penghitung yang tidak terpakai: tiga nilai yang tersebar dari 1 sampai 1.000.000 butuh sejuta penghitung. Ini juga langkah yang diulang radix sort untuk setiap digit.
Pertanyaan yang sering diajukan
Bagaimana cara kerja counting sort?
Ia menghitung berapa kali setiap nilai muncul, menjumlahkan hitungan untuk menemukan di mana blok setiap nilai dimulai, lalu memindahkan setiap nilai langsung ke tempat kosong berikutnya di bloknya. Ia tidak pernah membandingkan dua nilai.
Kapan sebaiknya memakai counting sort?
Saat nilainya bilangan bulat, atau bisa diubah menjadi bilangan bulat, dan rentang dari yang terkecil sampai yang terbesar tidak jauh lebih besar dari jumlah nilai: nilai rapor, usia, kode kecil. Dalam kasus itu waktunya sebanding dengan n + k.
Apakah counting sort stabil?
Ya, jika nilai dipindahkan sesuai urutan daftar ke tempat kosong berikutnya di bloknya, seperti di sini. Itulah yang membuat radix sort bisa memakainya untuk setiap digit.
Mengapa tidak menulis saja setiap nilai sebanyak hitungannya?
Untuk angka biasa itu berhasil, bahkan lebih sederhana. Tetapi data nyata biasanya membawa lebih dari sekadar kunci, misalnya nama pada setiap skor, dan menulis kunci hasil hitungan akan menghilangkannya. Memindahkan item itu sendiri menjaga semua yang melekat padanya.
Apakah angka saya dikirim ke mana pun?
Tidak. Pengurutan berjalan di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor