Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi


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



Download 1,4 Mb.
bet42/46
Sana15.04.2022
Hajmi1,4 Mb.
#555434
1   ...   38   39   40   41   42   43   44   45   46
Bog'liq
algoritmga kirish

Тўғридан-тўғри қўшиш усули билан саралаш
Бундай усул карта ўйинида кенг қўлланилади. Элементлар (картлар) ҳаёлан “тайёр” 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


алгоритм самарадорлиги
Фараз қилайлик, таққослашлар сони С, ўринлаштиришлар сони М бўлсин. Агар массив элементлари камайиш тартибида бўлса, у ҳолда тақққослашлар сони энг катта бўлиб, у га тенг бўлади, яъни . Ўринлаштиришлар сони эса га тенг бўлади, яъни . Агар берилган массив ўсиш тартибида сараланган бўлса, у ҳолда таққослашлар ва ўринлаштиришлар сони энг кичик бўлади, яъни , .
Тўғридан-тўғри танлаш усули билан саралаш
Фараз қилайлик, a1, a2, … , an элементлар кетма-кетлиги берилган бўлсин.
Мазкур усул қуйидаги тамойилларга асосланган:
1. Берилган элементлар ичидан энг кичик калитга эга элемент танланади.
2. Ушбу элемент бошланғич кетма-кетликдаги биринчи элемент a1 билан ўрин алмашади.
3. Ундан кейин ушбу жараён қолган n-1 та элемент, n-2 та элемент ва хоказо, токи битта энг “катта” элемент қолгунча давом эттирилади.

Таклиф қилинаётган усул алгоритми қуйидагича бўлади:


Паскал тилидаги дастури:
Procedure StraightSelection
Var
i,j,k: index; x:item;
begin
for i:=1 to n-1 do
k:=I; x:=a[i];
for j:=i+1 to n do
if a[j]end;
end;
a[k]:=a[i];
a[i]:=x
end;
end StraightSelection



Download 1,4 Mb.

Do'stlaringiz bilan baham:
1   ...   38   39   40   41   42   43   44   45   46




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish