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

Download 1.33 Mb. Pdf ko'rish
bet	44/49
Sana	20.08.2022
Hajmi	1.33 Mb.
	#25297

1 ... 41 42 43 44 45 46 47 48 49

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.

Download 1.33 Mb.

1 ... 41 42 43 44 45 46 47 48 49

Download 1.33 Mb.

Pdf ko'rish