3-Amali ish Tanlash va joylashtirish turkumidagi murakkablikga ega saralash algoritmlari. Tayanch so’zlar


 Ma’lumotlarning chiziqli tuzilmalarini saralashning asosiy usullari



Download 256,1 Kb.
Pdf ko'rish
bet4/4
Sana01.07.2022
Hajmi256,1 Kb.
#722368
1   2   3   4
Bog'liq
3-mavzu. Tanlash va joylashtirish turkumidagi murakkablikga ega

2. Ma’lumotlarning chiziqli tuzilmalarini saralashning asosiy usullari 
Istalgan usulda utkaziladigan saralash jarayoni bir necha tsikllardan iborat 
buladi. Har bir siklda yozuvlarning butun ketma-ketligi kurib chikiladi va uning 
elementlari bilan muayyan operatsiyalarni bajariladi. Ishlov berishning bir tsikli 
utish deb ataladi. 
Foydalanilayotgan saralash usuliga boglik xolda tartibga solingan ketma-
ketlik dastlabki ketma-ketlik joylashgan xotira uchastkasiga joylashtiriladi yoki uzi 
uchun xotiraning bush uchastkasini talab etadi. Biirinchi xolda usul xotira buyicha 
minimal xisoblanadi. Saralashning asosiy usullarini kurib chikamiz. 
Tanlash usuli. 
Ushbu usul bilan saralashda yozuvlarning tartibga solingan 
ketma-ketligi xotiraning dastlabki ketma-ketlik joylashgan uchastkasining uzida 
tashkil etiladi. Birinchi utish davomida eng kichik element izlanadi. Bu element 
topilganidan sung uni dastlabki ketma-ketlikdagi birinchi element bilan joyi 
almashtiriladi, natijada eng kichik element tuzilayotgan tartibga solingan ketma-
ketlikda birinchi xolatni egallaydi. Sungra kolgan elementlar ichidan keyingi eng 


kichik element izlanadi. Topilgan bu element xam dastlabki ketma-ketlikning 
ikkinchi elementi bilan joyi almashtiriladi. Ikkinchi utishdan sung ikki elementdan 
iborat bulgan ketma-ketlik tuzilgan buladi, ulardan birinchisi ikkinchisidan kichik 
buladi. Kalitining kiymati eng kichik bulgan keyingi elementni izlash va uni 
dastlabki ketma-ketlikning tegishli pozitsiyalariga joylashtirish barcha elementlar 
oshib boruvchi tartibda saralanib bulingunga kadar davom etadi. 
Tanlash usuli bilan saralash namunasi quyidagi rasmda keltirilgan. Saralash 
usullarini rasmlarda kursatishda yozuvlar fakat kalit maydonidan iborat deb kuzda 
tutiladi, 
ya’ni tartibga solinayotgan ketma-ketlik elementlari yozuvlar kalitining 
kiymatlari xisoblanadi. 10.1-rasmda belgilangan rakamlar ushbu utishda kalitining 
eng kichik kiymati buyicha tanlab olingan yozuvlarni bildiradi. Ushbu utish uchun 
kushalok chizikdan chapda joylashgan elementlar tartib buyicha kuyilgandir. 6 ta 
elementdan iborat bulgan yozuvlarning A ketma-ketligi besh utishda 
saralanibbuldi.Ushbuusulningtavsiflarinibaxolaymiz. N elementdan iborat ketma-
ketlikni saralash uchun N - 1 utish talab etiladi, chunki xar bir utishda tartibga 
solingan ketma-ketlikning xar bir tegishli fakat bitta element kiritiladi. I - utish 
uchun N - i solishtirish talab etiladi. Demak, solishtirishlarning umumiy soni 
Yukorida kurib chikilgan usul bilan saralashda solishtirishlar soni dastlabki 
ketma-ketlikning tartibga solinganlik darajasiga boglik bulmaydi. SHuning uchun 
olingan ifoda solishtirishlarning eng kam, eng kup va urtacha sonini anikdaydi. 
Solishtirishlarning urtacha sonini baxolash uchun ifodalarning kuyidagi 
approksimatsiyasidan foydalanish mumkin (1): 0,5 N
2
. Bunday approksimatsiya N 
= 100 ligida 1 % va N = 1000 ligida 0,1 % xatolikka yul kuyishi mumkin. Tanlash 
usuli bilan saralashda solishtirishlarning urtacha soni 0,5№ ga mutanosib deb 
xisoblash mumkin. 
Elementlarning joyini almashtirish mikdori dastlabki ketma-ketlik 
elementlarining joylashuviga boglikdir. Lekin istalgan xolda xam bitta utish 
davomida bittadan ortik bulmagan joy almashtirish talab etiladi; demak joy 


almashtirishlarning eng kup soni N-1 ga teng. Eng yaxshi xolda, ya’ni dastlabki 
ketma-ketlik tartibga solingan bulsa bitta xam joy almashtirish talab etilmaydi. 
Demak, joy almashtirishlar urtacha soni N/2 ga mutanosibdir. 

Download 256,1 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




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