- REJA :
- Saralash tushunchasi va uning vazifasi
- 2. Saralash masalasini formal qo‘yilishi
- 3. Ichki saralash usullari:Qat’iy usullar va yaxshilangan usullar
-
-
- 5-Mavzu: Ma'lumotlarni saralash algoritmlari. Saralashning qat’iy va yashilangan usullari
Saralash tushunchasi va uning vazifasi - Saralashdan maqsad - tartiblangan to‘plamda kerakli elementni topishni osonlashtirishdan iborat.
- Saralash – bu berilgan to‘plam elementlarini biror bir tartibda (o‘sish yoki kamayish) joylashtirish jarayonidir.
- dasturlarni translyasiya qilishda;
- ma’lumotlar majmuasini tashqi xotirada tashkil qilishda;
- kutubxonalar, kataloglar, ma’lumotlar bazasini yaratishda va boshq.
- Ma’lumotlarni xajmi va tuzilishiga nisbatan saralash usullari ikkiga ajraladi, ya’ni ichki va tashqi:
- ichki saralash – bu operativ xotiradagi saralash;
- tashqi saralash – tashqi xotirada saralash.
- Saralash masalasini formal qo‘yilishi
- Berilgan: a1, a2 ,…, an, ob’ektlar to‘plami.
- Talab qilinadi: Berilgan ob’ektlarni tartiblash, ularni shunday ap1, ap2 ,…, apn ketma-ketlikda o‘rinlashtirish lozimki, bunda ularning kalitlari kamaymaydigan tartibda joylashsin: kp1 kp2 … kpn.
- Saralash algoritmi turg‘un deyiladi, agarda saralash natijasida bir hil kalitli ob’ektlarlar bir-biriga nisbatan o‘rinlarini o‘zgartirmasa.
- saralashga ketgan vaqt (T(n)=C(n)+M(n), bunda C(n) - taqqoslashlar soni; M(n) - esa o‘rinlashtirishlar soni);
- dasturni ishlab chiqishga ketgan vaqt;
- talab qilinadigan xotira xajmi.
- Saralashga ketgan vaqt uchun quyidagi o‘rinli bo‘ladi:
- O(nlogn) T(n) O(n2);
- T(n)=O(n) – ideal holatda.
- Ob’ektlar hayolan “tayyor” a(1),...,a(i-1) va boshlang‘ich ketma-ketliklarga bo‘linadi. Har bir qadamda (i=2 dan boshlab) boshlang‘ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo‘shiladi.
- Misol: Faraz qilaylik, kalit qiymatlari 40,51,8,38,90,14,2,63 bo‘lgan ob’ektlar berilgan bo‘lsin.
- Qo‘yish orqali saralash algoritmi tahlili
- Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
Qo’yish orqali saralash usuli psevdocodi : - 1. Berilgan ob’ektlar ichidan eng kichik kalitga ega element tanlanadi.
- 2. Ushbu element boshlang‘ich ketma-ketlikdagi birinchi element a1 bilan o‘rin almashadi.
- 3. Undan keyin ushbu jarayon qolgan n-1 ta element, n-2 ta element va xokazo, toki bitta eng “katta” element qolguncha davom ettiriladi.
- Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
Tanlash orqali saralash algoritmi: - For i=1 to n-1
- x=a(i)
- K=I
- For j=i+1 to n
- if a(j)< x then
- k=j
- x=a(k)
- endif
- Next j
- a(k)=a(i)
- a(i)=x
- Next i return
- Almashtirish orqali saralash (Pufaksimon)
- n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo‘lsa, u holda ular o‘rni almashtiriladi.
- Almashtirish orqali saralash algoritmi tahlili
- Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
Almashtirish usuli uchun psevdokod: Bu ozgaruvchi agar birorta ham almashtitish bolmasa, false qiymat oladi. Quyida kerakli qo’shimchalar kursiv bilan ko’rsatilgan: - FL=TRUE
- For i=2 to n
- IF FL=FALSE THEN RETURN
- ENDIF
- FL=FALSE
- for j=n to I step -1
- if a(j)FL=TRUE
- x=a(j-1)
- a(j-1)=a(j)
- a(j)=
- endif
- next j
- next I
- Return
- i.
5-Mavzu bo‘yicha nazorat savollari - 1. Saralash deganda nima tushiniladi?
- 2. Saralashning vazifasi nimadan iborat?
- 3. Saralashning maqsadi nimadan iborat?
- 4. Qo‘yish orqali saralashning g‘oyasini tushuntirib bering?
- 5. Tanlash orqali saralash tushunchasi?
- 6. Pufaksimon saralash nima?
Do'stlaringiz bilan baham: |