|
Ma'lumotlarni saralash algoritmlari. Tad kafedrasi
|
| bet | 2/7 | | Sana | 19.11.2023 | | Hajmi | 20,41 Kb. | | #101203 |
Bog'liq Ma\'lumotlarni saralash algoritmlari. Saralash tushunchasi va uni-kompy.info HamdamovAyyubxon, ma\'lumotlar tuzulmasi va algaridimlar amaliy ish - 1, Ma\'lumotlar bazasi mustaqil ish -3, Mashinali o\'qitishga kirish 21-ma\'ruza Nosirov Kh, sun-iy-neyron-tarmoqlarni-umumiy-tasnifi, Mashinali o\'qitishga kirish 1-ma\'ruza Nosirov Kh (1), Asosnoma Quraqov S.A., Haydarqulov Shohzod, OR-5.51.02.02-Elektr atansiyalari tarmoqlari va tizimlari, lab5power point, Kompyuter tarmoqlari va adminstratorlash fanidan test savollari , 8-sinf mavzulashtirilgan testlar, menejment texSaralashning tadbiqi
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.
Samaradorlik mezonlari
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.
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 almashtirilib, massiv o’z joyida qoladi. Yuqoridagi usul adreslar jadvalini saralash usuli deyiladi.
Saralanayotganda bir hil kalitlar uchrashi mumkin, bu holda saralanagandan 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.
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.
|
| |
