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

Алгоритм таҳлили

Таҳлилни InsertionSort функциянинг чақирилишларини ва ҳар бир бу чақирилишлардаги рўйхат элементларини ҳисоблашдан бошлаймиз. 15 узунликдаги рўйхатга мурожаат қиламиз. Биринчи ўтишда ўзгарувчи increment нинг қиймати 7 га тенг, шунинг учун 2 узунликдаги рўйхатларда етти чақирилиш бажарилади. Иккинчи ўтишда ўзгарувчи increment нинг қиймати 3 га тенг, шунинг учун 5 узунликдаги рўйхатларда бешта чақирилиш бажарилади. Учинчи ва охирги ўтишда 15 узунликдаги рўйхатда битта чақириш бажарамиз. Олдинги натижалардан биламизки, икки элементли рўйхатда InsertionSort алгоритми энг ёмон ҳолда битта солиштириш бажаради. Энг ёмон ҳолда 5 элементли рўйхатда солиштиришлар сони 10 га тенг. 15 элементли рўйхатда эса солиштиришлар сони 105 га тенг. Бу барча сонларни қўшиб жами 142 солиштиришга эга бўламиз (7•1 + 3•10 + 1•105). Яхши баҳога эга бўлдик, аммо? Энг ёмон ҳолда қўйиш усулида ҳар бир янги элемент рўйхатнинг боштга қўшилишини эслайлик. ShellSort алгоритмининг охирги қадамида бу энг ёмон ҳолат амалга ошмайди, чунки олдинги қадамларда саралаш амалга оширилган. Балки бошқача ёндашиш ишнинг қолган ҳажмини ҳисоблашга ёрдам берар?

Саралаш алгоритмлари таҳлилида биз гоҳида рўйхатдаги инверсиялар сонини ҳисоблаймиз. Инверсия — бу рўйхатнинг тескари тартибда кетувчи жуфтларидир. Масалан, [3,2,4,1] рўйхатда тўрт инверсия мавжуд, яъни, (3,2), (3,1), (2,1) ва (4,1). Рўйхатда қанча инверсиялар кўп бўлса, у шунча тескари тартибда жойлашган бўлади ва уларнинг сони га тенг.

Саралаш алгоритмларини таҳлил қилишнинг усулларидан бири рўйхатнинг дастлабки ҳолатини сараланган рўйхатдан фарқли инверсияларни ҳисоблашдир. Ҳар элементлар ўрин алмаштирилишлари инверсиялар соонини ҳеч бўлмаганда бирга камайтиради. Масалан, агар пуфакча усули нотўғри тартибда жойлашган қўшни элементлар жуфтини текширишда уларнинг ўрин алмаштирилиши инверсиялар сонини бир аниқликда камайтиради. Ҳудди шундай қўйиш усулида ҳам катта элементни бир бирликка силжитиш инверсиялар сонини камайтиради. Шунинг учун пуфакча ва қўйиш усуллари солиштиришлари битта инверсияни йўқотади.

Шелл усули асосида қўйиш усули ётади, шу сабабли унга шундай таъкил ўринли. Аммо диққат қилсак Шелл усули аралаш қисм рўйхатларни тартибга солинади, алоҳида чақирилган солиштиришлардаги элементлар алмашинуви инверсиялар сонини бирдан ортиқ қийматга камайтириши мумкин. 3.1-расмда пиринчи ўтишда 16 ва 14 элементлар солиштирилди; уларнинг тартиби нотўғри эди ва улар алмаштирилди. 16 элементни биринчи ўриндан тўққизинчи ўринга қўйиб етти инверсиядан қутилдик. Шелл усули таҳлили 14 элементни сақловчи янги етти инверсияни ҳосил қилади. Шунинг учун у умумий инверсиялар сонини бирга камайтиради. Аммо бутунлигича ҳолат яхшиланади. Биринчи ўтишда саккиз солиштиришдан кейин 36 инверсия камайиши содир бўлади. Иккинчи ўтишда 19 солиштириш бажарилади ва 24 инверсия ўчирилади. Ниҳоят, охирги қадамда 19 солиштириш бажарилади ва 10 сўнгги инверсия ўчирилади. Солиштиришларнинг умумий сони 62 га тенг. Агар биз энг ёмон ҳолни ўртача ҳол билан алмаштирсак ҳам 152 солиштиришга эга бўламиз.

Шелл усулининг тўлиқ таҳлили жуда мураккаб ва биз унга тўхталмаймиз. Ушбу алгоритмнинг энг ёмон ҳолдаги таҳлили танланган қадамларда га тенглиги исботланган.