O’zbekiston respublikasi axborot texnologiyalai va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali


Download 172.5 Kb.
bet7/8
Sana17.01.2023
Hajmi172.5 Kb.
#1097909
1   2   3   4   5   6   7   8
Bog'liq
Standart ma\'lumotlar tuzilmalarini o\'rganish

Algoritm samaradorligi

Faraz qilaylik, taqqoslashlar soni C, o’rinlashtirishlar soni M bo’lsin. Agar massiv elementlari kamayish tartibida bo’lsa, u holda taqqoslashlar soni eng katta bo’lib, u ga teng bo’ladi, ya‟ni . O’rinlashtirishlar soni esa ga teng bo’ladi, ya‟ni . Agar berilgan massiv o’sish tartibida saralangan bo’lsa, u holda taqqoslashlar va o’rinlashtirishlar soni eng kichik bo’ladi, ya‟ni , .




Tanlash orqali saralash algoritmi

Mazkur usul quyidagi tamoyillarga asoslangan:


1. Eng kichik kalitga ega element tanlanadi.


2. Ushbu element birinchi element bilan o’rin almashinadi.


3. Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to bitta eng “katta” element qolguncha davom ettiriladi.


for(int i=0;i

for(int j=i+1;j

if (a[i] > a[j]){


int k = a[j];


a[j]= a[i];


a[i]= k;


}


Algoritm samaradorligi:

• Taqqoslashlar soni


S= N(N-1)/2=(N2-N)/2


• Massiv tartiblanganda o’rinlashtirishlar soni


Mmin=3(N-1)


• Massiv teskari tartiblanganda o’rinlashtirishlar soni


Mmin=MminN/2=3N(N-1)/2


Ushbu usul bo’yicha saralash bajarilsa, eng yomon holda taqqoslashlar va o’rinlashtirishlar soni tartibi n2 bo’ladi.




Pufaksimon saralash algoritmi

Ushbu usulning g’oyasi quyidagicha: 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 ularning o’rni almashtiriladi


“Pufaksimon” usulni yaxshilash


1) Agar massivda o’tishlar nafaqat yuqoridan pastga, balki bir vaqtning o’zida pastdan yuqoriga ham bo’lsa, u holda “yengil” elementlar “yuqoriga suzib” chiqadi va “og’ir” elementlar esa “cho’kadi”.


2) Massivda “bekor” o’tishni yo’q qilish uchun, tashqi siklda massiv saralanganligini tekshiruvchi belgi qo’yish lozim.


for (int i=0;i

for (int j=n-1;j>i;j--)


if (a[j] < a[j - 1]){


int x= a[j - 1];


a[j - 1] = a[j];


a[j] = x; }


O’rinlashtirish va taqqoslashlar soni: (n* log( n )).





Download 172.5 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




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