Kirish: I. Ma’lumotlar tuzilmasini saralash usullari

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