O’zbekiston respublikasi aloqa, axborotlashtirish va telekommunikatsiya texnologiyalari davlat qo’mitasi

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

^Cmax

_ nn 1 2
ga teng bo’ladi, ya’ni

On² . O’rinlashtirishlar soni esa

M_max  C_max  3(n 1)

ga teng bo’ladi, ya’ni

On² . Agar berilgan massiv o„sish

tartibida saralangan bo’lsa, u holda taqqoslashlar va o’rinlashtirishlar soni eng

kichik bo’ladi, ya’ni

C_min  n 1,

M_min  3(n 1) .

3. Tanlash orqali saralash algoritmi

Mazkur usul quyidagi tamoyillarga asoslangan:

1. 
   Eng kichik kalitga ega element tanlanadi.
   
2. 
   Ushbu element a₀ 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 a[j]){

int k = a[j];

a[j]= a[i];

a[i]= k;

}

Algoritm samaradorligi:

• 
  Taqqoslashlar soni
  

N


N²

C (N1)

2 2

• 
  Massiv tartiblanganda o’rinlashtirishlar soni
  

M_mi_n3(N1)

• 
  Massiv teskari tartiblanganda o’rinlashtirishlar soni
  

M ^N(N1)
ma^Mxmin³

2

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

4. 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 (6.1- rasm).

Misol : massiv - 4, 3, 7, 2, 1, 6.

6.1-rasm. Pufaksimon saralash usulida massiv elementlarining o’rnini almashtirish

Pufaksimon usulni massiv elementlarida pastdan yuqoriga va

yuqoridan pastga o’tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin.

Taqqoslashlar soni:

n n n²

M  

Almashtirishlar soni:

2 2 4

_n2 C_mzx3 ₄

“Pufaksimon” saralash usulini hisoblashga misol

6.2-rasm. Massivni pufaksimon saralashga misol

6.2-rasmda berilgan misolda 5 ta elementdan iborat massiv berilgan. Demak, massivda pastdan yuqoriga (yuqoridan pastga) o’tishlar soni 5-1=4 marta bo’ladi. Misoldan ko’rinib turibdiki, algoritm ichki siklda 3-qadamdan boshlab massivni “bekor” qayta ishlaydi, 4-qadamni bajarmasa ham bo’ladi.

Berilgan usullarning afzalligi:

1. 
   Eng sodda algoritm;
   
2. 
   Amalga oshirish sodda;
   
3. 
   Qo„shimcha o’zgaruvchilar shart emas. Kamchiliklari:
   

1. 
   Katta massivlarni uzoq qayta ishlaydi;
   
2. 
   Har qanday holatda ham o’tishlar soni kamaymaydi.