Saralash usullari mavzusi bo’yicha ma’ruza matni

2.1.4. Massivni oddiy almashtirish bilan saralash (“Pupakcha” usuli)

Berilgan algoritm massivning barcha elementlari saralangancha qo’shni elementlar juftligini taqqoslash va almashtirish tamoyiliga asoslangan. “Ko’piksimon” usilida saralash misoli 6-rasmda keltirilgan.
Shubhasiz, bu eng yomon holatda, kalit element minimal qiymati eng oxirgi o’ng elementga ega bolsa, qarashlar soni size-1 ga teng bo’ladi.
Saralashning samaradorligi. Bitta o’tish uchun o’rtacha taqqoslashlar sini С=size/2 ga teng. Bu holda mumkin bo’lgan uzatishlar soni М=1.5*С (tekshirilayotgan shart holatlarning yarmida bajariladi deb faraz qilamiz). O’tishlarning minimal miqdori 1 ga, maksimali − size -1, o’rtashasi esa − size/2 ga teng bo’ladi.
Shunday ekan,
; .

6-Rasm. Massivni oddiy almashtirish bilan saralashga misol

2.1.5. Piramidasimon saralash

Piramida barcha lar uchun , shartini bajaradigan kalitlarning ketma-ketligini
kabi aniqlanadi. Agar ikkiliq daraxt 1-rasmdagidek massiv ko’rinishida taqdim etilsa, u holda, shunday qilib, 2- va 3- rasmlardagi saralash daraxtti piramida bo’ladi va xususan, piramidaning elementi uning eng kichik elementi bo’ladi.
Endi ma’lim bir va qiymatlari uchun elementlari bilan piramida berilgan va kengaytirilgan piramidani tashkil qilish uchun yangi x elementni qo’shish kerak. Masalan, 2-rasmda ko’rsatilgan dastlabki piramidani olamiz va elementni qo’shib ushbu piramidani kengaytiramiz. x yangi element dastlab daraxning tepasiga joylashtiriladi, keyin esa u bilan elemenlarini taqqoslash bo’yicha kichilari joylashtirib, bir vaqtning o’zida yuqoriga ko’tariladigan yo’l-yo’lakay “galbir”dan o’tkazilip boriladi. Shunday qilib, yangi piramida yuzaga keladi. 8-rasmda piramidasimon saralash namoyish etiladi.



8-rasm. Daraxt qurish jarayoni
Berilgan misolda 44 qiymati dastlab 06 qiymati bilan o’rin almashadi, keyin 12 bilan, shunday qilib daraxt shakllanadi. Keyin elash jarayonini qo’yidagicha ifodalanadi: i, j – har bir qadamda o’rinlarini almashtirish kerak bo’lgan elementlarni ifodalovchi indekslar juftligi.
Bizning misolimizdagi sakkizta element uchun minimal va maksimal uzatishlar miqdori qo’yidagi boshlang’ich ketma-ketlikni beradi:
Мmin = 13 ketma-ketlik uchun
94, 67, 44, 55, 12, 42, 18, 6
Mmax=24 ketma-ketlik uchun
18, 42, 12, 44, 6, 55, 67, 94
Uzatishlarning o’rtacha soni nlog(n)/2 ga teng va og’ishi esa bu qiymatdan nisbatan kichik bo’ladi.