“Dasturiy injiniring” fakulteti “MA‟lumotlar tuzilmasi va algoritmlar”

 
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.