Sanab saralash (counting sort)
Hisoblash tartibi
Sanoqni saralash algoritmi massivni har bir qiymat sodir bo‘lish sonini hisoblash orqali tartiblaydi.
{{ msgDone }}
1 dan 5 gacha bo‘lgan 17 ta butun qiymatlar Counting Sort yordamida qanday tartiblanganligini ko‘rish uchun simulyatsiyani bajaring.
Hisoblash Saralash biz ko‘rib chiqqan oldingi tartiblash algoritmlari kabi qiymatlarni solishtirmaydi va faqat manfiy bo‘lmagan butun sonlarda ishlaydi.
Bundan tashqari, mumkin bo‘lgan qiymatlar diapazoni \(k\) qiymatlar sonidan \(n\) kichikroq bo‘lsa, hisoblash saralash tez ishlaydi.
Qanday ishlaydi:
- Turli xil qiymatlarning nechtasi borligini hisoblash uchun yangi massiv yarating.
- Saralash kerak bo‘lgan massivdan o‘ting.
- Har bir qiymat uchun tegishli indeksdagi hisoblash massivini oshirish orqali uni hisoblang.
- Qiymatlarni sanab bo‘lgach, tartiblangan massivni yaratish uchun hisoblash massividan o‘ting.
- Hisoblash massividagi har bir hisoblash uchun, hisoblash massivi indeksiga mos keladigan qiymatlar bilan to‘g‘ri elementlar sonini yarating.
Sanoqni saralash shartlari
Hisoblash tartibi faqat manfiy bo‘lmagan butun son qiymatlarining cheklangan diapazonida ishlaydi deb aytilishining sabablari quyidagilardir:
- Butun sonlar qiymatlari: Hisoblash saralash alohida qiymatlarni sanashga tayanadi, shuning uchun ular butun son bo‘lishi kerak. Butun sonlar bilan har bir qiymat indeksga mos keladi (manfiy bo‘lmagan qiymatlar uchun) va turli qiymatlarning cheklangan soni mavjud, shuning uchun \(k\) mumkin bo‘lgan turli qiymatlar soni \(n\) qiymatlari soniga nisbatan unchalik katta emas.
- Salbiy bo‘lmagan qiymatlar: Hisoblash saralash odatda hisoblash uchun massiv yaratish orqali amalga oshiriladi. Algoritm saralanadigan qiymatlardan o‘tganda, x indeksidagi hisoblash massiv qiymatini oshirish orqali x qiymati hisoblanadi. Agar biz salbiy qiymatlarni saralashga harakat qilsak, -3 qiymatini saralashda muammoga duch kelamiz, chunki indeks -3 hisoblash massividan tashqarida bo‘lar edi.
- Cheklangan qiymatlar diapazoni: Agar saralanishi mumkin bo‘lgan turli qiymatlar soni \(k\) tartiblanishi kerak bo‘lgan qiymatlar sonidan ko‘p bo‘lsa \(n\), biz saralash uchun kerak bo‘lgan hisoblash massivi bizda mavjud bo‘lgan saralashni talab qiladigan asl massivdan kattaroq bo‘ladi va algoritm samarasiz bo‘ladi.
Qo‘lda yugurish
Biz dasturlash tilida Counting Sort algoritmini amalga oshirishdan oldin, keling, qisqa massivni qo‘lda bajaramiz, shunchaki fikrni tushunish uchun.
1-qadam: Biz tartiblanmagan massivdan boshlaymiz.
myArray = [ 2, 3, 0, 2, 3, 2]
2-qadam: Biz har bir qiymatdan qancha borligini hisoblash uchun boshqa massiv yaratamiz. Massivda 0 dan 3 gacha bo‘lgan qiymatlarni saqlash uchun 4 ta element mavjud.
myArray = [ 2, 3, 0, 2, 3, 2]
countArray = [ 0, 0, 0, 0]
3-qadam: Endi hisoblashni boshlaylik. Birinchi element 2 ga teng, shuning uchun biz hisoblash massivi elementini indeks 2 ga oshirishimiz kerak.
myArray = [ 2, 3, 0, 2, 3, 2]
countArray = [ 0, 0, 1, 0]
4-qadam: Qiymatni hisoblagandan so‘ng, biz uni olib tashlashimiz va keyingi qiymatni hisoblashimiz mumkin, ya’ni 3.
myArray = [ 3, 0, 2, 3, 2]
countArray = [ 0, 0, 1, 1]
5-qadam: Biz hisoblaydigan keyingi qiymat 0 ga teng, shuning uchun biz hisoblash massivida 0 indeksini oshiramiz.
myArray = [ 0, 2, 3, 2]
countArray = [ 1, 0, 1, 1]
6-qadam: Barcha qiymatlar hisoblanmaguncha shunday davom etamiz.
myArray = [ ]
countArray = [ 1, 0, 3, 2]
7-qadam: Endi biz boshlang‘ich massivdagi elementlarni qayta yaratamiz va elementlarni eng pastdan yuqoriga tartiblash uchun qilamiz.
Hisoblash massividagi birinchi element bizda qiymati 0 bo‘lgan 1 ta element mavjudligini bildiradi. Shunday qilib, biz 0 qiymatiga ega 1 elementni massivga suramiz va hisoblash massividagi 0 indeksidagi elementni 1 ga kamaytiramiz.
myArray = [ 0]
countArray = [ 0, 0, 3, 2]
8-qadam: Hisoblash massividan biz 1-qiymatli elementlarni yaratishimiz shart emasligini ko‘ramiz.
myArray = [ 0]
countArray = [ 0, 0, 3, 2]
9-qadam: 2-qiymatli 3 ta elementni massiv oxiriga suramiz. Va biz ushbu elementlarni yaratishda biz 2-indeksdagi hisoblash massivini ham kamaytiramiz.
myArray = [ 0, 2, 2, 2]
countArray = [ 0, 0, 0, 2]
10-qadam: Nihoyat, massivning oxiriga qiymati 3 bo‘lgan 2 ta elementni qo‘shishimiz kerak.
myArray = [0, 2, 2, 2, 3, 3]
countArray = [ 0, 0, 0, 0]
Nihoyat! Massiv tartiblangan.
Yuqoridagi animatsiyali qadamlarni ko‘rish uchun quyidagi simulyatsiyani bajaring:
countArray = [
Python-da hisoblash tartibini amalga oshirish
Python dasturida Counting Sort algoritmini amalga oshirish uchun bizga kerak:
- Saralash uchun qiymatlari bo‘lgan massiv.
- Butun sonlar massivini qabul qiluvchi "countingSort" usuli.
- Qiymatlarni hisoblash uchun usul ichidagi massiv.
- Hisoblash massividagi elementlarni oshirish orqali qiymatlarni hisoblaydigan va olib tashlaydigan usul ichidagi sikl.
- Elementlar to‘g‘ri tartibda paydo bo‘lishi uchun hisoblash massividan foydalanib massivni qayta yaratadigan usul ichidagi sikl.
Yana bir narsa: hisoblash massivini to‘g‘ri o‘lchamda yaratish uchun massivdagi eng yuqori qiymat nima ekanligini aniqlashimiz kerak. Misol uchun, agar eng yuqori qiymat 5 bo‘lsa, barcha mumkin bo‘lgan manfiy bo‘lmagan 0, 1, 2, 3, 4 va 5 sonlarni hisoblash uchun hisoblash massivi jami 6 ta elementdan iborat bo‘lishi kerak.
Olingan kod quyidagicha ko‘rinadi:
Misol
Python dasturida hisoblash tartiblash algoritmidan foydalanish:
def countingSort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
while len(arr) > 0:
num = arr.pop(0)
count[num] += 1
for i in range(len(count)):
while count[i] > 0:
arr.append(i)
count[i] -= 1
return arr
mylist = [4, 2, 2, 6, 3, 3, 1, 6, 5, 2, 3]
mysortedlist = countingSort(mylist)
print(mysortedlist)
Misolni ishga tushirish »
Saralash vaqtini hisoblashning murakkabligi
Sanoqni saralash algoritmi qanchalik tez ishlashi mumkin bo‘lgan qiymatlar oralig‘iga \(k\) va qiymatlar soniga \(n\) bog‘liq.
Umuman olganda, tartiblashning vaqt murakkabligi \(O(n+k)\).
Eng yaxshi stsenariyda mumkin bo‘lgan turli qiymatlar diapazoni \(k\) qiymatlar soniga nisbatan juda kichikdir \(n\) va Hisoblash tartibida vaqt murakkabligi \(O(n)\).
Lekin eng yomon holatda, mumkin bo‘lgan turli qiymatlar diapazoni \(k\) qiymatlar soniga nisbatan juda katta bo‘lib, \(n\) qiymatlar soniga nisbatan juda katta bo‘lib, tartiblash vaqt murakkabligi \(O(n^2)\) yoki undan ham yomonroq bo‘lishi mumkin.
Quyidagi syujetda sanab saralash uchun vaqt murakkabligi qanchalik o‘zgarishi mumkinligini ko‘rsatadi.
Ko‘rib turganingizdek, algoritm sifatida tartiblash sanashini tanlashdan oldin qiymatlar oralig‘ini saralanadigan qiymatlar soniga nisbatan ko‘rib chiqish muhimdir. Bundan tashqari, sahifaning yuqori qismida aytib o‘tilganidek, hisoblash tartiblari faqat manfiy bo‘lmagan butun sonlar uchun ishlashini yodda tuting.
Yuqorida aytib o‘tilganidek: saralanadigan raqamlarning qiymati juda katta bo‘lsa (katta \(k\)) va tartiblash uchun bir nechta raqamlar bo‘lsa (kichik \(n\)), Sanoqni saralash algoritmi samarali emas.
Agar \(n\) va \(k\) ni o‘zgarmas holda ushlab tursak, yuqoridagi simulyatsiyadagi “Tasodifiy”, “Kamayuvchi” va “Ko‘tariluvchi” muqobillar bir xil miqdordagi operatsiyalarga olib keladi. Buning sababi shundaki, har uch holatda ham bir xil narsa sodir bo‘ladi: hisoblash massivi o‘rnatiladi, raqamlar hisoblanadi va yangi tartiblangan massiv yaratiladi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!