Адабиётлар

Тўғридан-тўғри қўшиш усули билан саралаш 
Бундай усул карта ўйинида кенг қўлланилади. Элементлар (картлар) 
ҳаѐлан ―тайѐр‖ a(1),...,a(i-1) ва бошланғич кетма-кетликларга бўлинади. Ҳар 
бир қадамда (i=2 дан бошланиб, ҳар бир қадамда бир бирликка ошириб 
борилади) бошланғич кетма-кетликдан i-чи элемент ажратиб олиниб тайѐр 
кетма-кетликнинг керакли жойига қўшилади. 

---

―Маълумотлар тузилмаси ва алгоритмлар‖ фанидан маърузалар матни.
муаллиф: Б.Б.Акбаралиев 
Таклиф қилинаѐтган усулни қуйидаги мисолда кўриб чиқамиз.
Фараз қилайлик, калит қиймати 4, 5, 3, 8, 1, 7 бўлган элементлар берилган 
бўлсин.
 
Керакли жойни қидириш жараѐнини қуйидаги тартибда олиб бориш 
қулай бўлади. Таққослашлар амалга ошириш мобайнида, навбатдаги 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
.