Python DSALesson 109Preview gratis
Counting Sort
Lesson ini bagian dari Python · Semua level
Ringkasan
Pelajaran ini menjelaskan Counting Sort, algoritma pengurutan non-comparison yang menghitung frekuensi kemunculan setiap nilai. Data kemudian ditulis ulang berdasarkan jumlah kumulatif dari setiap hitungan. Karena tidak membandingkan elemen satu sama lain, counting sort bisa mencapai O(n + k) untuk bilangan bulat dalam rentang yang relatif kecil.
Poin kunci
- Counting sort membuat array hitungan sepanjang rentang nilai (k) lalu mengisi frekuensi tiap angka.
- Setelah frekuensi diketahui, array keluaran diisi secara berurutan berdasarkan akumulasi hitungan.
- Kompleksitas waktu O(n + k) dengan n jumlah data dan k lebar rentang nilai.
- Cocok untuk bilangan bulat non-negatif dalam rentang kecil, tidak cocok untuk float dengan rentang luas.
- Counting sort stabil jika pengisian array keluaran dilakukan dari kanan ke kiri.
Materi lengkap
Contoh kode dan kuis
Materi lengkap, contoh kode, dan kuis tersedia untuk pelanggan. 5 soal.