Counting Sort

---

Vaqt murakkabligi nima ekani haqidagi umumiy tushuntirish uchun ushbu sahifaga qarang.

---

Counting Sort’ning vaqt murakkabligi

Counting Sort avval turli qiymatlarning necha marta uchrashini sanaydi, so‘ngra shu ma’lumotdan foydalanib massivni saralangan tartibda qayta tuzadi.

Umumiy qoida sifatida, Counting Sort algoritmi mumkin bo‘lgan qiymatlar diapazoni \(k\) qiymatlar soni \(n\) dan kichik bo‘lganda tez ishlaydi.

Vaqt murakkabligini Big O notatsiyasi bilan ifodalash uchun avval algoritm bajaradigan amallar sonini sanashimiz kerak:

• Maksimal qiymatni topish: har bir qiymat maksimal qiymat ekan-emasligini aniqlash uchun bir martadan tekshirilishi kerak, shuning uchun \(n\) ta amal kerak bo‘ladi.
• Sanash massivini initsializatsiya qilish: \(k\) massivdagi maksimal qiymat bo‘lsa, 0 ni ham qamrab olish uchun sanash massivida \(k+1\) ta element kerak. Sanash massividagi har bir element initsializatsiya qilinishi kerak, shuning uchun \(k+1\) ta amal kerak bo‘ladi.
• Saralamoqchi bo‘lgan har bir qiymat bir marta sanaladi, so‘ngra olib tashlanadi, ya’ni har bir sanash uchun 2 ta amal, jami \(2 \cdot n\) ta amal.
• Saralangan massivni qurish: saralangan massivda \(n\) ta element yaratiladi: \(n\) ta amal.

Jami quyidagini olamiz:

\[ \begin{equation} \begin{aligned} Amallar {} & = n + (k+1) + (2 \cdot n) + n \\ & = 4 \cdot n + k + 1 \\ & \approx 4 \cdot n + k \end{aligned} \end{equation} \]

Vaqt murakkabligi haqida avval ko‘rganlarimizga asoslanib, vaqt murakkabligini ifodalash uchun Big O notatsiyasidan foydalangan holda soddalashtirilgan ifoda tuzishimiz mumkin:

\[ \begin{equation} \begin{aligned} O(4 \cdot n + k) {} & = O(4 \cdot n) + O(k) \\ & = O(n) + O(k) \\ & = \underline{\underline{O(n+k)}} \end{aligned} \end{equation} \]

Counting Sort turli qiymatlar diapazoni \(k\) saralanishi kerak bo‘lgan qiymatlarning umumiy soni \(n\) ga nisbatan kichik bo‘lganda samarali ekani yuqorida aytib o‘tilgan edi. Endi buni bevosita Big O ifodasi \(O(n+k)\) dan ko‘rishimiz mumkin.

Masalan, turli sonlar diapazoni \(k\) saralanadigan qiymatlar sonidan 10 barobar katta ekanini tasavvur qiling. Bunday holatda algoritm vaqtining katta qismini turli sonlar diapazoni \(k\) ni qayta ishlashga sarflashini ko‘ramiz, garchi saralanishi kerak bo‘lgan qiymatlarning haqiqiy soni \(n\) unga nisbatan kichik bo‘lsa ham.

Counting Sort vaqt murakkabligini grafikda ko‘rsatish yoki avvalgi algoritmlardagidek vaqt murakkabligi uchun simulyatsiya yaratish oson emas, chunki vaqt murakkabligiga qiymatlar diapazoni \(k\) juda kuchli ta’sir qiladi.

Quyida Counting Sort vaqt murakkabligi qanchalik o‘zgarishi mumkinligini ko‘rsatuvchi grafik, undan keyin esa eng yaxshi va eng yomon holatlar izohi berilgan.

Counting Sort uchun eng yaxshi holat — diapazon \(k\) \(n\) ning kichik bir qismini tashkil etishi, aytaylik, \(k(n)=0.1 \cdot n\). Bunga misol sifatida, 100 ta qiymat uchun diapazon 0 dan 10 gacha, 1000 ta qiymat uchun esa 0 dan 100 gacha bo‘ladi. Bu holatda vaqt murakkabligi \(O(n+k)=O(n+0.1 \cdot n) = O(1.1 \cdot n)\) bo‘ladi va u \(O(n)\) ga soddalashtiriladi.

Eng yomon holat esa diapazon kiruvchi ma’lumotlardan ancha katta bo‘lganda yuzaga keladi. Aytaylik, atigi 10 ta qiymatdan iborat kiruvchi ma’lumot uchun diapazon 0 dan 100 gacha yoki, xuddi shunday, 1000 ta qiymatli kiruvchi ma’lumot uchun diapazon 0 dan 1000000 gacha. Bunday holatda \(k\) ning o‘sishi \(n\) ga nisbatan kvadratik bo‘ladi: \(k(n)=n^2\), va vaqt murakkabligi \(O(n+k)=O(n+n^2)\) bo‘lib, u \(O(n^2)\) ga soddalashtiriladi. Bundan ham yomonroq holatni tuzish mumkin, lekin bu holat nisbatan oson tushunilgani va, ehtimol, unchalik noreal ham emasligi uchun tanlandi.

Ko‘rib turganingizdek, Counting Sort algoritmini tanlashdan oldin qiymatlar diapazonini saralanadigan qiymatlar soni bilan solishtirib ko‘rish muhim. Shuningdek, sahifa boshida aytilganidek, Counting Sort faqat manfiy bo‘lmagan butun sonlar uchun ishlashini yodda tuting.

---

Counting Sort simulyatsiyasi

Amallar soni eng yomon holat \(O(n^2)\) (qizil chiziq) va eng yaxshi holat \(O(n)\) (yashil chiziq) oralig‘iga qanday tushishini ko‘rish uchun Counting Sort’ning turli simulyatsiyalarini ishga tushiring.

Avval aytib o‘tilganidek: agar saralanadigan sonlarning qiymatlari bir-biridan juda farq qilsa (katta \(k\)) va saralanadigan sonlar kam bo‘lsa (kichik \(n\)), Counting Sort algoritmi samarali emas.

Agar \(n\) va \(k\) ni o‘zgarmas qoldirsak, yuqoridagi simulyatsiyadagi "Tasodifiy", "Kamayish tartibida" va "O‘sish tartibida" variantlari bir xil miqdordagi amallarga olib keladi. Buning sababi, uchala holatda ham bir xil jarayon sodir bo‘ladi: sanash massivi tayyorlanadi, sonlar sanaladi va yangi saralangan massiv yaratiladi.

---

---