Reja : Saralash tushunchasi va uning vazifasi


Download 1.18 Mb.
Sana12.11.2020
Hajmi1.18 Mb.
#144217
Bog'liq
MTA 5 мавзу Саралаш 2020 2021

  • 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.
  • Izoh
  • Saralashbu 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.
  • Saralashning tadbiqi
  • 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.
  • Def.
  • 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.
  • Ichki saralash usullari
  • Qat’iy usullar
  • Yaxshilangan usullar
  • Algoritm g’oyasi
  • 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.
  • - boshlang’ich holat
  • Qo‘yish orqali saralash algoritmi tahlili
  • Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
  • Taqqoslashlar soni:
  • O‘rinlashtirishlar soni:
  • Saralashga ketgan vaqt:

Qo’yish orqali saralash usuli psevdocodi :

  • Qo’yish orqali saralash usuli psevdocodi :
  • For 1=2 to n
  • X=a(i)
  • for j=i-1 downto 1
  • if x
  • then a(j+1)=a(j)
  • Else go to L
  • endif
  • Next j
  • L : a(j+1)=x
  • Next I
  • return
  • Tanlash orqali saralash
  • 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.
  • Misol:
  • - boshlang’ich holat
  • Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
  • Taqqoslashlar soni:
  • O‘rinlashtirishlar soni:
  • Saralashga ketgan vaqt:

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)
  • Algoritm g’oyasi
  • 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.
  • Misol:
  • Almashtirish orqali saralash algoritmi tahlili
  • Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
  • Taqqoslashlar soni:
  • O‘rinlashtirishlar soni:
  • Saralashga ketgan vaqt:

Almashtirish usuli uchun psevdokod:

  • For i=2 to n
  • for j=n to I step -1
  • if a(j)
  • x=a(j-1)
  • a(j-1)=a(j)
  • a(j)=x
  • endif
  • next j
  • next I
  • Return
  • Bu holatda bitta bo’sh o’tish bo’ladi.Elementlarni ortiqcha almashtirmaslik uchun fl o’zgaruvchi (flajok) kirinish mumkin.

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?

Download 1.18 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling