8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja

Sanash orqali saralash (Counting sort). r - l hajmli massiv yarating, massivning l - minimal va r maksimal elementi hisoblanadi. Shundan so‘ng, massiv orqali borib va har bir element sonini hisoblang. Endi qiymatlar massividan o‘tib, har bir sonni nechta marta bo‘lganini yozishingiz mumkin. murakkabligi O(n+ r - l) bo‘ladi. Bu algoritm barqaror qilish uchun o‘zgartirishingiz mumkin: buning uchun, keyingi soni joyini aniqlash kerak bo‘lib va chapdan o‘ngga orginal massiv orqali borish, to‘g‘ri joyda elementi qo‘yib va o‘rnini birga oshirish lozim. Bu saralash sinovdan o‘tkazilmagan, testlar yetarli darajada katta raqamlar uchun mavjud, chunki yangi massiv yaratish ancha xotira talab qiladi. Biroq, bu algoritm masalaga qarab foydali bo‘ldi.
Blok orqali saralash (Bucket sort). Bu algoritm savat va cho‘ntak saralash sifatida tanilgan algoritmdir. Massivning l minimal va r maksimal elementi bo‘lsin. Elementlarni bloklarga ajratamiz, birinchi blokda l dan l + k gacha, ikkinchisiga l + k dan l + 2k gacha va hokazo elementlarni o‘z ichiga oladi, bu yerda k = (r – l) /n, n bloklar soni. Umuman olganda, agar bloklar soni ikkiga teng bo‘lsa, bu algoritm tezkor saralashga aylanadi. Ushbu algoritmning murakkabligi aniq emas, maʻlumotlariga murojaat vaqt va bloklar soniga bog‘liq. Muvaffaqiyatli maʻlumotlar bo‘yicha ish vaqti chiziqli ekanligi aytib o‘tiladi. Ushbu algoritmni amalga oshirish eng qiyin vazifalardan biri ekanligini isbotlangan. Buni shunchaki yangi massivlar yaratish, ularni rekursiv saralash va ularni bir-biriga birlashtirish orqali amalga oshirishingiz mumkin. Biroq, bu yondashuv juda sekin va men qoniqmadim. Samarali amalga oshirishda bir necha g‘oyalardan foydalaniladi:

1. 
   yangi massivlar yaratmaymiz. Buning uchun sanao‘ orqali saralash texnikasidan foydalanamiz: har bir blokdagi elementlar sonini, prefiks summalarini va shu tariqa har bir elementning massivdagi o‘rnini sanaymiz.
   
2. 
   Bo‘sh bloklardan boshlamaymiz. Bo‘sh bo‘lmagan bloklarning indekslarini alohida massivda kiritish va ulardan boshlash orqali saralash.
   
3. 
   Massiv tartiblanganligini tekshiramiz. Agar hali ham minimal va maksimal topish uchun bir o‘tish qilish kerak, chunki, bu ishlayotgan vaqt yomonlashmaydi, lekin elementlar orginal massiv bir xil tartibda yangi bloklari joylashtirilgan, chunki u qisman tartiblashtirilgan maʻlumotlarni saralashni tezlashtirish uchun algoritmni beradi.
   
4. 
   Algoritm juda noqulay bo‘lgani uchun, u juda kam sonli elementlar bilan juda samarasiz. Joylashtirishga o‘tish tartibida ishni taxminan 10 martagacha tezlashtiradi.
   

Bu faqat qancha bloklar tanlashni tushunishga qolmoqda. Randomize testlarda quyidagi ballarni olishga muvaffaq bo‘lgan: 1500 elementlari uchun 107 bloklari va 3000 uchun 108 ta. Murakkablik formulasini topa olmadik, ish vaqti bir necha marta yomonlashadi.