Texnalogiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot

x 
elementi oldida uning kalitidan kichik kalitli 
a(j) 
elementi chiqqanda.
2. 
x 
elementi oldida element qolmaganda.
for (int i=1;i
while(a[j]
int t=a[j-1]; 
a[j-1]=a[j]; 
a[j]=t; 
j=j-1; 
} 
} 
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=(N
2
-N)/2 
 
Massiv tartiblanganda o’rinlashtirishlar soni
M
min
=3(N-1) 
 
Massiv teskari tartiblanganda o’rinlashtirishlar soni
M
min
=M
min
N/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 (1- rasm).
Misol : 
massiv - 4, 3, 7, 2, 1, 6.

---

1-rasm. Pufaksimon saralash usulida massivelementlarining o’rnini almashtirish
Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan pastga o’tishni bir 
vaqtda amalga oshirish natijasida yaxshilash mumkin.
Taqqoslashlar soni:
M=(n/2)(n/2)=n
2
/4
Almashtirishlar soni:
C
max
=3n
2
/4
2-rasm. Massivni pufaksimon saralashga misol 
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.
“