|
Ma'lumotlarni saralash algoritmlari. Saralash tushunchasi va uning vazifasi. Saralashning qat’iy usullari va ularning samaradorligi
|
| bet | 2/7 | | Sana | 28.11.2023 | | Hajmi | 7,87 Mb. | | #107179 |
Bog'liq FpicbbEWsfTs6uumr4wrAPbc2neimBs1pzBMGjHx (1)Saralashning tadbiqi
Saralash masalasini formal qo‘yilishi
Berilgan: a1, a2 ,…, an, ob’ektlar to‘plami.
Talab qilinadi: Berilgan ob’ektlarni tartiblash, yani 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.
YA’NI: Saralanayotganda bir hil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir hil kalitlilar boshlang’ich tartibda qanday joylashgan bo’lsa, ushbu tartibda qoldirilishi maqsadga muvofiq bo’ladi (Bir hil kalitlilar o’zlariga nisbatan).
Bunday usulga turg’un saralash deyiladi.
Samaradorlik mezonlari
1.Saralashga ketgan vaqt (T(n)=C(n)+M(n), bunda C(n) - taqqoslashlar soni; M(n) - esa o‘rinlashtirishlar soni);
2.Dasturni ishlab chiqishga ketgan vaqt;
3.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.
Agar saralanayotgan yozuvlar xotirada katta xajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma’nosida) talab qiladi.
Ushbu sarfni kamaytishi maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma’lumot ko’rsatkichlari(kalitlar) almashtirilib, massiv o’z joyida qoladi. Yuqoridagi usul adreslar jadvalini saralash usuli deyiladi.
Ma’lumotlarni xajmi va tuzilishiga nisbatan saralash usullari ikkiga ajraladi, ya’ni ichki va tashqi:
Ichki saralash usullari
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Ma'lumotlarni saralash algoritmlari. Saralash tushunchasi va uning vazifasi. Saralashning qat’iy usullari va ularning samaradorligi
|
