8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja


Sanash orqali saralash (Counting sort)



Download 184,65 Kb.
bet6/14
Sana06.08.2022
Hajmi184,65 Kb.
#846556
1   2   3   4   5   6   7   8   9   ...   14
Bog'liq
8-m

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.

Download 184,65 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   14




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish