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

2.1.3. Қидириш алгоритмларининг қиёсий ҳарактеристикалари

Сараланмаган файллар ва массивлар учун бир тур қидириш усуллари ишлатилса, сараланган файл ва массивлар учун бошқа турдаги қидириш алгоритмлари ишлатилади. Қуйида уларнинг айримлари билан танишамиз:

№	Алгоритм номи	Қийинлик баҳоси	Афзаллиги	Камчилиги
1	Кетма-кет қидириш	O((n-m+1)m)	Сараланмаган массивларда ишлатилади, оддий, кичик рўйхатларда жуда тез	Катта рўйхатларда секин ишлайди
2	Иккилик қидириш	O(log n)	Катта рўйхат-ларда тез иш-лайди, сатрли маълумотлар билан енгил ишлайди
3	Интерполоцион қидириш	O(log n)	Катта рўйхат-ларда тез иш-лайди	Мураккаб, сатрли маълумотлар билан қийин ишлайди

2.2. Саралаш алгоритмлари ва уларни баҳолаш

Ушбу бўлимда дастурлаштиришда кенг ишлатиладиган саралаш алгоритмларини қараймиз. Иккилик қидириш кетма-кет қидиришга қараган вақтни тежаши шарофати билан дастурий таъминотлар яратувчилари маълумотларни гоҳида сараланган шаклда сақлашни таъкидлашади. Бу эса керакли маълумотни қидиришда иккилик ёки бошқа усуллардан фойдаланиш имконини беради.

Биз ўрганадиган барча алгоритмлар рўйхатни калит қийматнинг ўсиш тартибида саралайди. Калит тури ҳар хил бўлиши – бутун, белгили қатор ёки қандайдир мураккаб бўлиши мумкин ва биз калитлар жуфтини солиштириш амалидан фойдаланамиз. Оддийлик учун барча калит қийматлар фарақли деб фараз қиламиз.

2.2.1. Ўрнига қўйиш усули билан саралаш алгоритми

Қўйиш усулининг асосий ғояси қарийб сараланган рўйхатга янги элементни қўшишда у ихтиёрий жойидан керакли жойга қўйиш ва рўйхатни қайта саралашдир. Бунда дастлабки рўйхатнинг биринчи элементидан бир элементли сараланган рўйхат тузилади. Кейин дастлабки рўйхатнинг иккинчи элементи сараланган бир элементли рўйхатнинг тегишли жойига қўйилади ва натижада икки элементли сараланган рўйхат ҳосил бўлади. Энди дастлабки рўйхатнинг учинчи элементини сараланган икки элементли рўйхатнинг керакли жойига қўйиш мумкин. Бу жараён то дастлабки рўйхатнинг барча элементлари ушбу рўйхатнинг сараланган қисмида жойлашгунча давом эттирилади.

Ушбу жараённи амалга оширувчи алгоритм қуйидагича:

InsertionSort(list,N)

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

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

for i=2 to N do

newElement=list[i]

location=i-1

while(location >= 1) and (list[location]>newElement) do

// барча катта элементларни бир ўринга силжитамиз

list [location+1]=list[location]

location=location-1

end while

list[location+1]=newElement

end for

Бу алгоритм янги қўйиладиган элементни newElement ўзгарувчига таъминлайди. Кейин массивдаги барча катта элементлар бир ўринга силжиб ушбу янги элементга жой ажратилади. Циклнинг охирги итерацияси location+1 рақамли элементни location+2 ўринга кўчиради. Бу шуни билдирадики location+1 ўрин «янги» элемент учун бўшатилади.

Энг ёмон ҳолат таҳлили

Агар ички while циклига қарасак кўриш мумкинки, агар ҳар сафар янги қўшиладиган элемент сараланган қисм барча элементларидан кичик бўлса, у ҳолда энг кўп амаллар бажарилади. Бу ҳолда цикл иши location ўзгарувчи 0 га тенг бўлганда тўхтайди. Шунинг учун алгоритм энг кўп ишни янги элементни рўйхат бошига қўйганда бажаради. Бу ҳолат берилган рўйхат камайиш тартибида сараланган ҳолда юз беради ва бу энг ёмон ҳол ҳисобланади.

Ушбу ҳолдаги жараённи кўрамиз. Биринчи ўринга рўйхатнинг иккинчи элементи қўйилади. У атиги битта элемент билан солиштирилади. Иккинчи қўйиладиган элемент (тартиб бўйича учинчи) олдинги иккитаси билан солиштирилади, учинчи қўйиладиган элемент эса олдинги уч элемент билан; умуман, i- қўйиладиган элемент олдинги i та элемент билан солиштирилади ва бу жараён N-1 марта бажарилади. Шу туфайли қўйиш усули билан саралашнинг энг ёмон ҳолдаги қийинлиги қуйидагига тенг





Ўртача ҳол таҳлили

Ўртача ҳол таҳлилини икки босқичга ажратамиз. Дастлаб навбатдаги элементнинг ўрнини аниқлаш учун керак бўлган ўртача солиштиришлар сонини ҳисоблаймиз. Кейин барча керакли амалларни биринчи босқич натижалари орқали ҳисоблаш мумкин. Ишни i- элемент ўрнини аниқлаш учун керак бўлган ўртача солиштиришлар сонини ҳисоблашдан бошлаймиз. Юқорида айтганимиздек i-элементни қўшиш ҳеч бўлмаганда битта солиштиришни талаб қилади.

i – элемент учун нечта мумкин бўлган ўринлар бор? Кичик рўйхатни қарймиз ва натижани ихтиёрий ҳол учун умумийлаштирамиз. Биринчи қўшиладиган элемент учун икки имконият мавжуд: у икки элементли сараланган рўйхатда биринчи ёки иккинчи бўлиши мумкин. Иккинчи қўшиладиган элементда 1, 2 ва 3 рақамли учтадан бир ўрин бор. Демак, i –қўшиладиган элемент учун i+1 дан бир мумкин бўлган ўринлар бор. Бу барча имкониятлар тенг эҳтимолли деб фараз қиламиз.

Ҳар қайси i + 1 мумкин бўлган ўринларга бориш учун нечта солиштириш талаб қилиниди? Яна i нинг кичик қийматларини қараймиз ва натижани умумлаштиришга ҳаракат қиламиз. Агар тўртинчи қўшиладиган элемент 5 ўринга тушса, у ҳолда биринчи солиштириш ёлғон бўлади. Агар тўғри ўрни 4 бўлса, у ҳолда биринчи солиштириш рост иккинчиси эса – ёлғон. 3- ўринга тушишда биринчи ва иккинчи солиштиришлар рост, учинчиси эса– ёлғон. 2- ўринда биринчи, иккинчи ва учинчи солиштиришлар муваффақиятли, тўртинчи эса – йўқ. Биринчи ўринга тушишда биринчи, иккинчи, учинчи ва тўртинчи солиштиришлар рост, ёлғон солиштиришлар бўлмайди. Бу шуни билдирадики, i + 1, i, i- 1, . . . , 2 ўринларга тушувчи i – элемент учун солиштиришлар сони мос равишда 1, 2, 3, ... , i бўлади, биринчи ўринга тушишда солиштиришлар сони i га тенг. i – элементни қўйиш учун солиштиришларнинг ўртача сони қуйидаги тенглик билан берилади



Биз i – элементни қўйишдаги ўртача амаллар сонини ҳисобладик. Энди бу натижаларни N- 1 элементли рўйхат учун йиғиш керак:



(1.11) формулани икки марта қўллаб ҳосил қиламиз



(1.9) ва (1.10) тенгликлардан фойдаланиб қуйидагига эга бўламиз



Энди (1.15), (1.14) ва (1.20) тенгликлар қуйидагини беради