Ma'lumotlarni saralash algoritmlari. Saralash tushunchasi va uning vazifasi. Saralashning qat’iy usullari va ularning samaradorligi

Download 7,87 Mb.
bet	2/7
Sana	28.11.2023
Hajmi	7,87 Mb.
	#107179

1 2 3 4 5 6 7

Bog'liq
FpicbbEWsfTs6uumr4wrAPbc2neimBs1pzBMGjHx (1)
Маруза матни 21йил, MI, 1. Andy Smart, Мустақил иши, 5-sinf 9-dars shablon na\'muna

O( nlogn )  T( n )  O( n2 ); T( n )=O( n )

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 – bu operativ xotiradagi saralash;
tashqi saralash – tashqi xotirada saralash.

Ichki saralash usullari

Download 7,87 Mb.

1 2 3 4 5 6 7

Download 7,87 Mb.