10
Faraz
qilaylik,
taqqoslashlar soni S, o’rinlashtirishlar soni M bo’lsin. Agar
massiv elementlari kamayish tartibida bo’lsa, u holda taqqqoslashlar 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
.
To’g’ridan-to’g’ri tanlash usuli bilan saralash
Faraz qilaylik, a
1
, a
2
, … , a
n
elementlar ketma-ketligi berilgan bo’lsin.
Mazkur usul quyidagi tamoyillarga asoslangan:
1. Berilgan elementlar ichidan eng kichik kalitga ega element tanlanadi.
2. Ushbu element boshlang’ich ketma-ketlikdagi birinchi element a
1
bilan
o’rin almashadi.
3. Undan keyin ushbu jarayon qolgan n-1 ta element, n-2 ta element va xokazo,
toki bitta eng “katta” element qolguncha davom ettiriladi.
Algoritm samaradorligi:
Taqqoslashlar soni M =
n
n
n
n
2
1
2
2
(
)
.
Almashtirishlar soni C
min
= 3(n - 1), C
max
= 3(n - 1)
n
2
(n
2
tartib).
Ushbu usul bo’yicha
saralash bajarilsa, eng yomon
xolda taqqoslashlar va
almashtirishlar
soni tartibi n
2
bo’ladi.
