Мундарижа Кириш

2.2.3. Шелл усули билан саралаш алгоритми

Шелл усулини Дональд Л. Шелл ўйлаб топган. Унинг ғайриоддийлиги шуки, у бутун рўйхатни аралаш қисм рўйхатлар жамланмаси сифатида қарайди. Биринчи қадамда бу қисм рўйхатлар оддий элементлар жуфтини намоён қилади. Иккинчи қадамда ҳар қайси гуруҳда тўрттадан элемент. Жараённинг такрорланишида ҳар бир қисм рўйхатдаги элементлар сони ортади, қисм тўпламлар сони эса мос равишда камаяди. 3.1-расмда 16 элеентдан иборат рўйхатни саралашда қўллаш мумкин бўлган қисм рўйхатлар тасвирланган.

3.1(а)-расмда ҳар бирида икки элементдан саккизта қисм рўйхат тасвирланган, қайсики биринчи қисм рўйхат биринчи ва тўққизинчи элементни олган, иккинчи қисм рўйхат – иккинчи ва ўнинчи элементларни ва ҳ.к. 3.1(б)-расмда ҳар бирида тўрттадан элемент бўлган тўртта қисм рўйхатни кўряпмиз. Бу сафар биринчи қисм рўйхат биринчи, бешинчи, тўққизинчи ва ўн учинчи элементлардан таркиб топган. Иккинчи қисм рўйхат иккинчи, олтинчи, ўнинчи ва ўн тўртинчи элементлардан тузилган. 3.1(д)-расмда икки қисм рўйхат мос ҳолда тоқ ва жуфт рақамли элементлардан таркиб топгпн шакл кўрсатилган. 3.1 (е)-расмда биз яна битта рўйхатга келамиз.

(a) 1- o`tish

(b) 2- o`tish

(d) 3- o`tish

(t) 4-o`tish

3.1-расм. Шелл усулининг тўрт ўтиши

Қисм рўйхатларни саралаш қўйиш усули орқали амалга оширилади.натижада қуйидаги алгоритмга эга бўламиз:

Shellsort(list,N)

list сараланадиган рўйхат

N рўйхатдаги элементлар сони

passes = [log_2 N]

while (passes>=1) do

increment=2^passes-1

for start=1 to increment do

InsertionSort(list,N,start,increment)

end for

passes=passes-1

end while

Ўзгарувчи increment қисм рўйхат элементлари орасидаги қадам ўлчамини ифодалайди. (3.1-расмда қадам 8, 4, 2 ва 1 қийматларни қабул қилади). Алгоритмни рўйхат элементлари узунлигидан кичик, иккининг энг катта даражасидан 1 га кам қадамдан бошлаймиз. Шу сабали 1000 элементли рўйхат учун қадамнинг биринчи қиймати 511 га тенг. Қадам қиймати яна қисм рўйхатлар сонига ҳам тенг. Биринчи қисм тўплам элементлари 1 ва 1+increment рақамларга эга; охирги қисм тўпламнинг биринчи элементи increment рақамли элементдир.

while циклининг охирги бажарилишида ўзгарувчи passes 1 га тенг бўлади, шу туфайли InsertionSort функциянинг охирги чақирилишида increment ўзгарувчининг қиймати 1 га тенг.

Ушбу алгоритмнинг таҳлили ички InsertionSort алгоритмига асосланади. ShellSort алгоритмининг таҳлилига киришишдан олдин шуни эслатиб ўтамизки, қўйиш усули билан саралаш алгоритми N элементдан иборат рўйхатда энг ёмон ҳолда амаллар талаб қилади, ўртача ҳолда эса у амаллар талаб қилади.