1.6. Tanlash usuli.
Ushbu usul bilan saralashda yozuvlarning tartibga solingan ketma-ketligi xotiraning dastlabki ketma-ketlik joylashgan uchastkasining o’zida tashkil etiladi. Birinchi o’tish davomida eng kichik element izlanadi. Bu element topilganidan so’ng uni dastlabki ketma- ketlikdagi birinchi element bilan joyi almashtiriladi, natijada eng kichik element tuzilayotgan tartibga solingan ketma-ketlikda birinchi holatni egallaydi. So’ngra qolgan elementlar ichidan keyingi eng kichik element izlanadi. Topilgan bu element ham dastlabki ketma-ketlikning ikkinchi elementi bilan joyi almashtiriladi. Ikkinchi o’tishdan so’ng ikki elementdan iborat bo’lgan ketma-ketlik tuzilgan bo’ladi, ulardan birinchisi ikkinchisidan
kichik bo’ladi. Kalitining qiymati eng kichik bo’lgan keyingi elementni
izlash va uni dastlabki ketma-ketlikning tegishli pozitsiyalariga joylashtirish barcha elementlar oshib boruvchi tartibda saralanib bo’lingunga qadar davom etadi.
Tanlash usuli bilan saralash namunasi 6.1-rasmda keltirilgan.
Saralash usullarini rasmlarda ko’rsatishda yozuvlar faqat kalit maydonidan
iborat deb ko’zda tutiladi, ya’ni tartibga solinayotgan ketma-ketlik
elementlari yozuvlar kalitining qiymatlari hisoblanadi. 6.1-rasmda
belgilangan raqamlar ushbu o’tishda kalitining eng kichik qiymati
bo’yicha tanlab olingan yozuvlarni bildiradi. Ushbu o’tish uchun
qo’shaloq chiziqdan chapda joylashgan elementlar tartib bo’yicha
qo’yilgandir. 6 ta elementdan iborat bo’lgan yozuvlarning A ketma-ketligi
besh o’tishda saralanib bo’ldi. Ushbu usulning tavsiflarini baholaymiz. N
elementdan iborat ketma-ketlikni saralash uchun N - 1 o’tish talab etiladi,
chunki har bir o’tishda tartibga solingan ketma-ketlikning har bir tegishli faqat bitta element kiritiladi. I - o’tish uchun N - i solishtirish talab etiladi. Demak,
solishtirishlarning umumiy soni
Yuqorida ko’rib chiqilgan usul bilan saralashda solishtirishlar soni
dastlabki ketma-ketlikning tartibga solinganlik darajasiga bog’liq bo’lmaydi.
SHuning uchun olingan ifoda solishtirishlarning eng kam, eng ko’p va
o’rtacha sonini aniqlaydi. Solishtirishlarning o’rtacha sonini baholash uchun ifodalarning quyidagi approksimatsiyasidan foydalanish mumkin (1): 0,5 N2.
Bunday approksimatsiya N = 100 ligida 1 % va N = 1000 ligida 0,1 %
xatolikka yo’l qo’yishi mumkin. Tanlash usuli bilan saralashda
solishtirishlarning o’rtacha soni 0,5№ ga mutanosib deb hisoblash mumkin.
Elementlarning joyini almashtirish miqdori dastlabki ketma-ketlik
elementlarining joylashuviga bog’liqdir. Lekin istalgan holda ham bitta
o’tish davomida bittadan ortiq bo’lmagan joy almashtirish talab etiladi;
demak joy almashtirishlarning eng ko’p soni N - 1 ga teng. Eng yaxshi
holda, ya’ni dastlabki ketma-ketlik tartibga solingan bo’lsa bitta ham joy
almashtirish talab etilmaydi. Demak, joy almashtirishlar o’rtacha soni N/2. ga mutanosibdir.
i 1 2 3 4 5 6
A(i ) 10 4 11 9 7 2
1 утиш 2 4 11 9 7 10
2 утиш 2 4 11 9 7 10
3 утиш 2 4 7 9 11 10
4 утиш 2 4 7 9 11 10
5 утиш 2 4 7 9 10 11
Do'stlaringiz bilan baham: |