3-mavzu. Tanlash va joylashtirish turkumidagi murakkablikga ega saralash algoritmlari. Reja

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². 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.