“Ахборот технологиялари” факультети “Ахборот технологияларини дастурий таъминоти” кафедраси “маълумотлар тузилмаси ва алгоритмлар”

Танлаш орқали саралаш 
Мазкур усул қуйидаги тамойилларга асосланган: 
1. Энг кичик калитга эга элемент танланади. 
2. Ушбу элемент 
1
a
биринчи элемент билан ўрин алмашинади. 
3. Кейин мазкур жараён қолган n-1, n-2 элементлар билан такрорланиб, то битта энг “катта” элемент 
қолгунча давом эттирилади. 
for i := 1 to n - 1 do 
begin 
x := a[i]; 
k := i; 
for j := i + 1 to n do 
if a[j] < x then
begin 
k := j; 
x := a[k]; 
end; 
a[k] := a[i]; 
a[i] := x; 
end; 

---

36
Алгоритм самарадорлиги: 
 Таққослашлар сони 
2
)
1
(
2
2
N
N
N
N
C





 Массив тартибланганда ўринлаштиришлар сони 
)
1
(
3
min



N
M
 Массив тескари тартибланганда ўринлаштиришлар сони 
2
)
1
(
3
2
min
max
N
N
N
M
M






Ушбу усул бўйича саралаш бажарилса, энг ёмон холда таққослашлар ва ўринлаштиришлар сони тартиби 
n
2
бўлади. 
 
Пуфаксимон саралаш 
Ушбу усулни ғояси қуйидагича: n - 1 марта массивда қуйидан юқорига қараб юриб калитлар жуфти-
жуфти билан таққосланади. Агар пастки калит қиймати юқоридаги жуфти калитидан кичик бўлса, у ҳолда улар 
ўрни алмаштирилади. 
Мисол : массив - 4, 3, 7, 2, 1, 6. 
Пуфаксимон усулни массив элементларида пастдан-тепага ва тепадан-пастга ўтишни бир вақтда амалга 
ошириш натижасида яхшилаш мумкин. 
Таққослашлар сони: 
4
2
2
2
n
n
n
M



Алмаштиришлар сони: 
4
3
2
n
C
mzx


“Пуфаксимон” саралаш усулини ҳисоблашга мисол 
Берилган мисолда 5 та элементдан иборат массив берилган. Демак, массивда пастдан юқорига (юқоридан 
пастга) ўтишлар сони 5-1=4 марта бўлади. Мисолдан кўриниб турибдики, алгоритм ички циклда 3 қадамдан 
бошлаб массивни “бекор” қайта ишлайди, 4-қадамни бажармаса ҳам бўлади. 
Берилган усуллнинг афзаллиги: 
1) Энг содда алгоритм; 
2) амалга ошириш содда; 
3) қўшимча ўзгарувчилар шарт эмас. 
Камчиликлари: 
1) Катта массивларни узоқ қайта ишлайди; 
2) Ҳар қандай ҳолатда ҳам ўтишлар сони камаймайди 

---

37
Quiksort – тез саралаш усули