Menghitung bekerja Urutkan dengan menghitung kejadian dari masing-masing nilai data. Ini mengasumsikan bahwa ada n item data dalam kisaran 1 .. k, dimana k adalah integer. Algoritma kemudian dapat menentukan, untuk setiap elemen input, jumlah elemen kurang dari itu. Misalnya jika ada 9 elemen kurang dari x elemen, maka x termasuk dalam data posisi 10.
Algoritma Menghitung Urut pseudocode adalah sebagai berikut:
countingsort (A [], B [], k) untuk i = 1 untuk k lakukan C [i] = 0
untuk j = 1 ke panjang (A) lakukan C [A [j]] = C [A [j]] + 1
untuk 2 = 1 untuk k lakukan C [i] = C [i] + C [i-1]
untuk j = 1 ke panjang (A) lakukan B [C [A [j]]] = A [j] C [A [j]] = C [A [j]] - 1
Meskipun ini mungkin terlihat rumit, sebenarnya merupakan algoritma yang sangat sederhana dan pintar.
Array A [] menyimpan data awal yang akan diurutkan.
Array C [] digunakan untuk menghitung kejadian dari nilai data
Array B [] digunakan untuk menyimpan, akhir diurutkan, daftar.
Yang pertama untuk loop Menginisialisasi C [] nol atas. Yang kedua untuk kenaikan nilai loop di C [], menurut frekuensi mereka dalam data. Yang ketiga untuk loop menambahkan semua nilai sebelumnya, membuat C [] mengandung total kumulatif. Keempat untuk loop menulis keluar data diurutkan ke array B [].
Dua dari untuk loop mengambil O (k) waktu, dan dua mengambil O (n) waktu. Poin penting untuk dicatat adalah bahwa Urut Menghitung stabil: Semua elemen nilai yang sama akan muncul dalam urutan yang sama dalam array output array yang mereka lakukan dalam array input.
Tidak ada komentar:
Posting Komentar