16-ma’ruza. Qidiruv va saralash. Оddiy almashtirish usuli bilan saralash

16-ma’ruza. Qidiruv va saralash.

Оddiy almashtirish usuli bilan saralash.

Saralash – deb biror bir to`plam elementlarini o`sish yoki kamayish boyicha tartiblangan ketmaketilgiga aytiladi. Odatda saralanadigan elementlar sonli va simvolli(lexikagrafik) bo`lishi mumkin. Boshqa algaritmlarni samaradorligini oshirish uchun saralash algaritmlari muxim. Oddiy almshtirish usuli bilan saralash
Almashtirish usuli (pufakcha). Bu usul bilan saralashda tartibga solingan ketma-ketlik xotiraning dastlabki ketma-ketlik joylashgan erida tashkil etiladi. Saralash jarayonida qo`shish elementlarini juftlab solishtiriladi. Agar solishtirilayotgan elementlar o`rtasidagi tartib buzilgan bo`lsa ularning joylari almashtiriladi. Bu almashtirish usuli ko`pincha pufakcha usuli xam deb ataladi. Chunki eng kichik elementlar xar bir o`tishda xuddi pufakchalarga o`xshab ketma-ketlikning birinchi pozitsiyasi yo`nalishida ‘qalqib ’ chiqadi. 10.2- rasmda pufakcha usulida saralash namunasi keltirilgan . birinchi o`tish davomida A1 va A2 elementlari solishtiriladi. Agar A2Xar bir keyingi o`tishda navbatdagi eng katta elementlar tegishlicha N-1 ,N-2 va xakoza pozitsiyalarni egallaydi. Natijada tartibga solingan massiv tuziladi.
Xar bir o`tishdan so`ng ushbu o`tish davomida joy almashtirishlar bo`lmagan – bo`lmaganligini tekshirib qo`yish mumkin. Agar joy almashtirishlar bo`lmagan bo`lsa , bu ketma-ketlik tartibga solinmaganligi va keyingi o`tishlar talob etilmasligini bildiradi. O`tishlar davomida almashtirishlar ishtirok etadigan oxirgi element (10.2 – bu elementlar ko`sh chiziq bilan chizilgan). Navbatdagi o`tishda tagiga chizilgan element va va barcha undan keyingi elementlarni solishtirishda ishtirok etmaydi , chunki shu pozitsiyadan boshlab ketma-ketlik tartibga solingan bo`ladi.
Bu usul uchun solishtirishlar soni saralash uchun zarur bo`ladigan o`tishlar soniga bog`liq. Eng yamon xolda , yani ketma-ketlik teskari tartibda bo`lsa , xar bir i- o`tishda almashtirishlar bajariladi. O`tishlar soni esa N- 1 ga teng. Bunda saralash uchun almashtirishlar soni eng ko`p bo`ladi. Cmax (N-1) + (N-2) +(N-3) + + 1 arifmetik pragretsiya azolari summasiga teng.

yani Cmax=

Eng yaxshi xolda , dastlabki ketma-ketlik tartbga solingan bor – yo`g`i bitta o`tish va N-1 solishtirishlar talab etiladi. Solishtirishlarning eng kam soni Cmin = N-1 . solishtirishning o`rtacha soni 0.25N² .

Pufakcha usulida saralashda almashtirishlar soni dastlabki ketma-ketlikning tartibga solinganlik darajasiga bog`liq bo`ladi. Agar dastlabki ketma-ketlik to`la tartibga solingan bo`lsa , almashtirishlar yo`q. Dastlabki ketma-ketlik teskari tartibda tartibga solingan bo`lsa , yani kalitining qiymati kamayib boorish tartibda joylashgan yozuvlarni kalitining qiymati oshib boorish tartibda saralash zarur bo`lganda, almashtirishlar soni eng ko`p bo`ladi. Bu xolda almashtirish xar ir solishtirishda bo`ladi va umumiy almashtirishlar soni 0.5 N (N-1 ) gat eng bo`ladi. O`rtacha almashtirishlar soni 0.25 N² mutanasibdir.