16-ma’ruza. Qidiruv va saralash. Оddiy almashtirish usuli bilan saralash
Download 23.19 Kb.
|
1 2
Bog'liqMaruza-15
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 A2 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.25N2 . 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 N2 mutanasibdir. Download 23.19 Kb. Do'stlaringiz bilan baham: |
1 2
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling