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

Тўғридан-тўғри қўшиш усули билан саралаш 

---

35
Бундай усул карта ўйинида кенг қўлланилади. Элементлар (картлар) ҳаёлан “тайёр” a(1),...,a(i-1) ва 
бошланғич кетма-кетликларга бўлинади. Ҳар бир қадамда (i=2 дан бошланиб, ҳар бир қадамда бир бирликка 
ошириб борилади) бошланғич кетма-кетликдан i-чи элемент ажратиб олиниб тайёр кетма-кетликнинг керакли 
жойига қўшилади. 
Алгоритм 
Тўғридан-тўғри қўшиш орқали саралаш алгоритми қуйидагича бўлади: 
for x:=2 to n do 
x:=a[i] 
х ни a[1]...a[i] оралиқ мос жойига қўшиш 
end 
Керакли жойни қидириш жараёнини қуйидаги тартибда олиб бориш қулай бўлади. Таққослашлар амалга 
ошириш мобайнида, навбатдаги a(j) элемент билан солиштирилади, кейин эса х бўш жойга қўйилади ёки a( j ) 
ўнга сурилади ва жараён чапга “кетади”. Шуни эътиборга олиш лозимки, саралаш жараёни қуйидаги шартларни 
бирортаси бажарилганда якунланади: 
1. х элементи калитидан кичик калитли a(j) элемент топилди. 
2. тайёр кетма-кетликнинг чап томони охирига етиб борилди. 
Procedure StraightInsertion 
Var 
i,j:index; x:item; 
begin 
for i:=2 to n do 
x:=a[i]; a[0]:=x; j:=1; 
while xa[j]:=x 
end 
end StraightInsertion 
 
алгоритм самарадорлиги 
Фараз қилайлик, таққослашлар сони С, ўринлаштиришлар сони М бўлсин. Агар массив элементлари 
камайиш тартибида бўлса, у ҳолда тақққослашлар сони энг катта бўлиб, у 
 
2
1
max


n
n
C
га тенг бўлади, 
яъни 
 
2
n
O
. Ўринлаштиришлар сони эса 
)
1
(
3
max
max



n
C
M
га тенг бўлади, яъни 
 
2
n
O
. Агар берилган 
массив ўсиш тартибида сараланган бўлса, у ҳолда таққослашлар ва ўринлаштиришлар сони энг кичик бўлади, 
яъни 
1
min


n
C
, 
)
1
(
3
min


n
M
.