O„zbekiston respublikasi aloqa, axborotlashtirish va telekommunikatsiya texnologiyalari davlat qo„mitasi toshkent axborot texnologiyalari universiteti

x 
elementi oldida uning kalitidan kichik kalitli 
a(j)
 elementi chiqqanda. 
2. 
x
 elementi oldida element qolmaganda. 
for (int i=1;i

---

 
113 
 
      int j=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 


2
1
max


n
n
C
  ga  teng  bo„ladi,  ya‟ni 
 
2
n
O
.  O„rinlashtirishlar  soni  esa 
)
1
(
3
max
max



n
C
M
  ga  teng  bo„ladi,  ya‟ni 
 
2
n
O
.  Agar  berilgan  massiv  o„sish 
tartibida  saralangan  bo„lsa,  u  holda  taqqoslashlar  va  o„rinlashtirishlar  soni  eng 
kichik bo„ladi, ya‟ni 
1
min


n
C
, 
)
1
(
3
min


n
M
.  
 
6.3.
 
Tanlash orqali saralash algoritmi 
 
Mazkur usul quyidagi tamoyillarga asoslangan: 
1. Eng kichik kalitga ega element tanlanadi. 
2. Ushbu element 
0
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
for(int j=i+1;j
      if (a[i] > a[j]){ 
         int k = a[j]; 
          a[j]= a[i]; 

---

 
114 
          a[i]= k; 
          }      
 
Algoritm samaradorligi: 

 
Taqqoslashlar soni 
2
)
1
(
2
2
N
N
N
N
C





 

 
Massiv tartiblanganda o„rinlashtirishlar soni 
)
1
(
3
min



N
M
 

 
Massiv teskari tartiblanganda o„rinlashtirishlar soni 
2
)
1
(
3
2
min
max
N
N
N
M
M






 
Ushbu  usul  bo„yicha  saralash  bajarilsa,  eng  yomon  holda  taqqoslashlar  va 
o„rinlashtirishlar soni tartibi n
2
 bo„ladi. 
 
6.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 

---

 
115 
 
yuqoridan pastga o„tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin. 
Taqqoslashlar soni: 
4
2
2
2
n
n
n
M



 
Almashtirishlar soni: 
4
3
2
n
C
mzx


 
“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.