Saralash usullari mavzusi bo’yicha ma’ruza matni

2.1.2. Massivni oddiy tanlash bilan saralash

Bu usul qo’yidagi qoydalarga asoslangan:
Qiymati eng katta element tanlanadi. U oxirgi arr [s-1] element bilan joyini almashtiradi. Keyin bu amallar qolgan s-1 elementlar bilan, keyin dastlabki s-2 elementler bilan va h.k. faqat birinshi element eng kichik bo’lgangacha qaytalanadi. Masalan oddiy tanlash bilan saralash usuli 4-rasmda ko’rsatilgan.
Oddiy tanlash bilan saralashning samaradorligi. Kalitlarni taqqoslashlar soni kalitning dastlabki tartibiga bog’liq emas. Taqqoslash amallari k o’zgaruvchi bilan boshqariladigan tsikl tanasida boshqariladi va o’rtasha qaytalashlar soni size/2 bo’ladi. Bu tsikl o’z navbatida L o’zgaruvchi bilan boshqariladigan tcikl tanasida joylashgan bo’ladi va qaytalashlar soni size-1 bo’ladi. Shunday qilib, taqqoslashlar soni bo'ladi.
Uzatishlari soni, aksincha, kalitlari dastlabki maqsadida bog'liq.
Agar k bo’yicha tsikl tanasida taqqoslash amallari yarmi “rost” natijasini bersa, u holda bu tsiklda uzatishlarning o’rtacha soni size/4 bo’ladi. Yo’qorida ko’rsatiganidek, L bo’yicha tsikl size-1 marta va tsikl tanasi ichida bo’lsa k tsikl va uchta uzatishlar bajariladi. Ushbu hisobda uzatishlar soni:
М= (3+ size/4) * (size −1)
Oddiy tanlash bilan saralash usulida taqqoslashlar va uzatishlar sonida mutanosib ravishda ni olamiz.

4-rasm. Massivni oddiy tanlash bilash saralash

2.1.3. Massivni oddiy joylashtirish bilan saralash

Oddiy qo’yish usuli massivning barcha elementlarini dastlab faqat bitta elementdan iborat tartiblangan qismga va tartiblanmagan qismga ajratishni taklif qiladi. Tartiblanmagan qismidan navbatdagi element uning elementlari bilan taqqoslashlardan o’tib tartiblangan qismidagi ma’lum bir joyiga qoyiladi. Munosib joyni qidirishda taqqoslashlarni va uzatishlarni qo’lay almashlab turish, ya’niy, tanlangan elementni navbatdagi a[j] element bilan uni taqqoslab va o’ngga yoki chapga harakatlanuvchi a[i] ni yoki uzatib, yoki taqqoslab “g’albir”dan o’tkazish. “G’albir” dan o’tkazish qo’yidagi ikki sharoitga tugatilishini eslatib o’tamiz: x kalitidan kichik kalitli a[j] element topilganda yoki tayyorlangan ketma-ketlik nihoyasiga etganda. Bunda tartiblangan qismi bitta elementga uzayadi. Saralash tartiblanmagan qismi tugatilishi bilan tamomlanadi.
Berilgan saralashda taqqoslashlarning umumiy soni taxminan
,
ga teng. Bu holda, P berilganlar bo’yicha o’tishlar soni talab etiladi.

5-rasmda oddiy qo’yish saralash usulini qadamba-qadam qaraymiz.

5-rasm. Massivni oddiy kiritish bilan saralashga misol
Kalitlarni taqqoslashing C_i soni i-“g’albir”dan o’kazishda eng kattasi i-1 ga, eng kichigi esa 1 ga, agar n kalitlarning barcha joy alsmashishlar ehtimoli teng deb taxmin qilsak i/2 ga teng bo’ladi. Mi uzatishlar (o’zlashtirishlar) soni (tosiq bilan) C_i+2 ga teng. Shuning uchun taqqoslashlar va uzatishlar soni
Cmin = n-1 Mmin = 2 (n-1)
Cср. = (n²+n-2) /4 Mср. = (n²+9n-10) /4
Cmax = ( (n²+n) - 1) /2 Mmax = (n²+3n-4) /2.
Oddiy kiritishlar bilan saralash algoritmini osongina yaxshilash mumki, ya’niy avval tartiblangan tayyor a[1], … ,a[i-1] ketma-ketligini foydalangan holda yangi elementni kiritish kerak. Shuning uchun kiritish joylarini sezilarli darajada tez topish uchun, tayyor ketma-ketlikning o’rta qiymatini tekshiradigan va kiritish joyi topilmaguncha ikkiga bo’lish davom ettiriladigan ikkilik izlashni qo’llash mumkin.