DSA Counting Sort (sanab saralash)

Counting Sort

Counting Sort algoritmi har bir qiymat necha marta uchrashini sanash orqali massivni saralaydi.

1 dan 5 gacha bo‘lgan 17 ta butun son qiymati Counting Sort yordamida qanday saralanishini ko‘rish uchun simulyatsiyani ishga tushiring.

Counting Sort biz ko‘rib chiqqan oldingi saralash algoritmlari kabi qiymatlarni taqqoslamaydi va faqat manfiy bo‘lmagan butun sonlar bilan ishlaydi.

Bundan tashqari, mumkin bo‘lgan qiymatlar oralig‘i \(k\) qiymatlar soni \(n\) dan kichik bo‘lganda Counting Sort tez ishlaydi.

Counting Sort uchun shartlar

Counting Sort faqat cheklangan oraliqdagi manfiy bo‘lmagan butun son qiymatlari uchun ishlaydi, deyilishining sabablari quyidagilar:

• Butun son qiymatlari: Counting Sort turli qiymatlarning necha marta uchrashini sanashga tayanadi, shuning uchun ular butun son bo‘lishi kerak. Butun sonlarda har bir qiymat (manfiy bo‘lmagan qiymatlar uchun) indeksga mos keladi va turli qiymatlar soni cheklangan bo‘ladi, shuning uchun mumkin bo‘lgan turli qiymatlar soni \(k\) qiymatlar soni \(n\) ga nisbatan unchalik katta bo‘lmaydi.
• Manfiy bo‘lmagan qiymatlar: Counting Sort odatda sanash uchun massiv yaratish orqali amalga oshiriladi. Algoritm saralanadigan qiymatlar bo‘ylab o‘tganda, x qiymati sanash massivining x indeksidagi qiymatni oshirish orqali sanaladi. Agar manfiy qiymatlarni saralashga harakat qilsak, -3 qiymatini saralashda muammoga duch kelardik, chunki -3 indeksi sanash massividan tashqarida bo‘lardi.
• Qiymatlarning cheklangan oralig‘i: Agar saralanadigan mumkin bo‘lgan turli qiymatlar soni \(k\) saralanadigan qiymatlar soni \(n\) dan katta bo‘lsa, saralash uchun kerak bo‘ladigan sanash massivi saralanishi lozim bo‘lgan dastlabki massivimizdan kattaroq bo‘ladi va algoritm samarasiz bo‘lib qoladi.

Qo‘lda bajarib ko‘rish

Counting Sort algoritmini dasturlash tilida amalga oshirishdan oldin, g‘oyani tushunib olish uchun qisqa massiv bo‘ylab qo‘lda o‘tib chiqaylik.

1-qadam: Saralanmagan massivdan boshlaymiz.

2-qadam: Har bir qiymatdan nechtadan borligini sanash uchun yana bitta massiv yaratamiz. 0 dan 3 gacha bo‘lgan qiymatlarni hisobga olish uchun massiv 4 ta elementga ega.

3-qadam: Endi sanashni boshlaymiz. Birinchi element 2 ga teng, shuning uchun sanash massivining 2 indeksidagi elementni bittaga oshirishimiz kerak.

4-qadam: Qiymatni sanab bo‘lgach, uni o‘chirib, keyingi qiymatni — 3 ni sanashimiz mumkin.

5-qadam: Navbatdagi sanaladigan qiymat 0, shuning uchun sanash massivida 0 indeksini bittaga oshiramiz.

6-qadam: Barcha qiymatlar sanalguncha shu tarzda davom etamiz.

7-qadam: Endi dastlabki massiv elementlarini qayta yaratamiz va buni elementlar eng kichigidan eng kattasigacha tartiblangan bo‘ladigan qilib bajaramiz.

Sanash massividagi birinchi element bizda 0 qiymatli 1 ta element borligini bildiradi. Shuning uchun massivga 0 qiymatli 1 ta elementni qo‘shamiz va sanash massivining 0 indeksidagi elementni 1 ga kamaytiramiz.

8-qadam: Sanash massividan 1 qiymatli hech qanday element yaratishimiz shart emasligini ko‘ramiz.

9-qadam: Massiv oxiriga 2 qiymatli 3 ta element qo‘shamiz. Bu elementlarni yaratish jarayonida sanash massivining 2 indeksidagi qiymatni ham kamaytirib boramiz.

10-qadam: Nihoyat, massiv oxiriga 3 qiymatli 2 ta element qo‘shishimiz kerak.

Nihoyat! Massiv saralandi.

Yuqoridagi qadamlarni animatsiyada ko‘rish uchun quyidagi simulyatsiyani ishga tushiring:

Qo‘lda bajarib ko‘rish: nima sodir bo‘ldi?

Algoritmni dasturlash tilida amalga oshirishdan oldin yuqorida nima sodir bo‘lganini batafsilroq ko‘rib chiqishimiz kerak.

Counting Sort algoritmi ikki bosqichda ishlashini ko‘rdik:

1. Har bir qiymat sanash massivining tegishli indeksidagi sonni bittaga oshirish orqali sanaladi. Qiymat sanalgach, u o‘chiriladi.
2. Qiymatlar sanash massividagi son va shu sonning indeksi yordamida to‘g‘ri tartibda qayta yaratiladi.

Buni yodda tutgan holda, algoritmni Python yordamida amalga oshirishni boshlashimiz mumkin.

Counting Sort’ni amalga oshirish

Counting Sort algoritmini dasturlash tilida amalga oshirish uchun bizga quyidagilar kerak:

1. Saralanadigan qiymatlarga ega massiv.
2. Butun sonlar massivini qabul qiladigan "countingSort" metodi.
3. Qiymatlar sonini hisobga olib borish uchun metod ichidagi massiv.
4. Sanash massividagi elementlarni bittaga oshirish orqali qiymatlarni sanaydigan va o‘chiradigan, metod ichidagi sikl.
5. Elementlar to‘g‘ri tartibda joylashishi uchun sanash massivi yordamida massivni qayta yaratadigan, metod ichidagi sikl.

Yana bir narsa: Sanash massivini to‘g‘ri o‘lchamda yaratish uchun massivdagi eng katta qiymat qancha ekanini aniqlashimiz kerak. Masalan, agar eng katta qiymat 5 bo‘lsa, barcha mumkin bo‘lgan manfiy bo‘lmagan butun sonlar — 0, 1, 2, 3, 4 va 5 ni sanay olish uchun sanash massivi jami 6 ta elementdan iborat bo‘lishi kerak.

Natijaviy kod quyidagicha ko‘rinadi:

def countingSort(arr):
    if not arr:
        return arr
        
    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1
        
    arr[:] = []

    for num, freq in enumerate(count):
        arr.extend([num] * freq)

    return arr

unsortedArr = [4, 2, 2, 6, 3, 3, 1, 6, 5, 2, 3]
sortedArr = countingSort(unsortedArr)
print("Sorted array:", sortedArr)

Counting Sort’ning vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Counting Sort vaqt murakkabligi haqida yanada chuqurroq va batafsil tushuntirish uchun ushbu sahifaga tashrif buyuring.

Counting Sort algoritmi qanchalik tez ishlashi mumkin bo‘lgan qiymatlar oralig‘i \(k\) ga ham, qiymatlar soni \(n\) ga ham bog‘liq.

Umuman olganda, Counting Sort’ning vaqt murakkabligi \(O(n+k)\) ga teng.

Eng yaxshi holatda mumkin bo‘lgan turli qiymatlar oralig‘i \(k\) qiymatlar soni \(n\) ga nisbatan juda kichik bo‘ladi va Counting Sort’ning vaqt murakkabligi \(O(n)\) bo‘ladi.

Ammo eng yomon holatda mumkin bo‘lgan turli qiymatlar oralig‘i \(k\) qiymatlar soni \(n\) ga nisbatan juda katta bo‘ladi va Counting Sort’ning vaqt murakkabligi \(O(n^2)\) yoki undan ham yomonroq bo‘lishi mumkin.

Quyidagi grafik Counting Sort’ning vaqt murakkabligi qanchalik o‘zgarishi mumkinligini ko‘rsatadi.

Ko‘rib turganingizdek, Counting Sort’ni algoritm sifatida tanlashdan oldin qiymatlar oralig‘ini saralanadigan qiymatlar soni bilan solishtirib ko‘rish muhim. Shuningdek, sahifa boshida aytib o‘tilganidek, Counting Sort faqat manfiy bo‘lmagan butun son qiymatlari uchun ishlashini yodda tuting.

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.

[,,,4,2,1]