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

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.