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

2.2.2. Ўрин алмаштириш (пуфакча) усули билан саралаш алгоритми

Энди пуфакча усули саралаш алгоритмини қараймиз. Унинг асосий принципи кичик элементларнинг рўйхат учига отлиб чиқиши ва бу вақтда катта қийматлар пастга тушади. Бу усулнинг турли хиллари мавжуд. Биз улардан бирини қараймиз.

Пуфакча усули саралаш алгоритми рўйхат бўйича бир қанча ўтиш бажаради. Ҳар бир ўтишда қўшни элементлар солиштирилиши бажарилади. Агар қўшни элементлар тартиби нотўғри бўлса, у ҳолда уларнинг ўрни алмаштирилади. Ҳар бир ўтиш рўйхат бошидан бошланади. Дастлаб биринчи ва иккинчи элементлар солиштирилади, кейин иккинчи ва учинчи, сўнг учинчи ва тўртинчи ва ҳ.к. ; нотўғри тартибдаги элементлар жуфтда алмаштирилади. Биринчи ўтишда энг катта элемент учраса, у ҳолда у кейинги барча рўйхат элементлари билан алмаштириладива бу жараён рўйхат охиригача бажарилади. Шу туфайли иккинчи ўтишда охирги элемент билан солиштиришнинг аҳамияти йўқ. Иккинчи ўтишда катталиги бўйича иккинчи элемент рўйхатнинг охиридан иккинчи ўрнига туширилади. Бу жараённинг ҳар бир ўтишдаги такрорийлиги навбатдаги элементларнинг ўз ўрнини топишини таъминлайди. Бу жараёнда кичик элементлар ҳам юқорига тўпланади. Агар қайсидир ўтишда ҳеч қандай алмаштириш бажарилмаса, у ҳолда барча элементлар ўз жойида бўлади ва алгоритм бажарилишини тўхтатиш мумкин. Кузатиш мумкинки, ҳар бир ўтишда бир қанча элементлар силжийди ва битта элементгина ўзининг ўрнини қатъий эгаллайди.

Пуфакча усули саралаш алгоритмининг кўриниши қуйидагича:
BubbleSort(list,N)

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

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

numberOfPairs=N

swappedElemens=true

while swappedElements do

numberOfPairs=numberOfPairs-1

swappedElements=false

for i=1 to numberОfPairs do

if list [i] > list[i+1] then

Swap(list[i] , list[i+1])

swappedElements=true

end if

end for

end while

Энг яхши ҳол таҳлили

swappedElements нинг нотўғри интерпретациясини огоҳлантириш мақсадида энг яхши ҳолни қисқача қараймиз. Қайси ҳолда бажариладиган иш ҳажми кичик бўлишини қараймиз. Биринчи ўтишда for цикли тўлиқ бажарилиши керак ва шунинг учун алгоритмга энг камида N - 1 солиштириш талаб қилинади. Икки ҳолатни қарашга тўғри келади: биринчи ўтишда ҳеч бўлмаганда битта ўрин алмаштириш ва ўрин алмаштиришлар бўлмаган ҳоллар. Биринчи ҳолда алмаштириш swappedElements қийматини true га ўзгартиради ва демак, while цикли такрорий бажарилади, яъни яна N-2 солиштириш талаб қилади. Иккинчи ҳолда swappedElements мантиқий ифода false қиймат олади ва алгоритм бажарилиши тўхтатилади.

Шу сабабли энг яхши ҳолда N-1 солиштириш бажарилади. Бу шуни кўрсатадики, маълумотларнинг энг яхши тўплами бу – талаб қилинган тартибдаги элементлардан тузилган рўйхатдир.

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

Энг яхши ҳолни талаб қилинган тартибда берилган рўйхат таъминласа, уларнинг тескари ҳолати энг ёмон ҳолни келтириб чиқаради. Бунда биринчи элемент рўйхат охирига қадар ҳар қайси элемент билан солиштирилади. Бу жараён барча қолган элементлар учун такрорланади, шунинг учун for цикли N -1 марта такрорланади. Шу туфайли камайиш тартибидаги рўйхат энг ёмон ҳолатга олиб келади.

Энг ёмон ҳола нечта солиштириш бажарилади? Биринчи ўтишда N - 1 та қўшни қийматлар солиштирилиши бажарилади, иккинчисида – N-2 солиштиришлар. Кейингилари шуни кўрсатадики, ҳар бир навбатдаги ўтишда солиштиришлар сони бирга камаяди. Демак энг ёмон ҳолат қийинлиги қуйидаги формула билан аниқланади



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

Юқорида айтганимиздек энг ёмон ҳолда for цикли N - 1 марта такрорланади. Ўртача ҳолда исталган бу моментларда алмаштиришларсиз ўтишлар тенг эҳтимолли деб фараз қиламиз. Ҳар бир ҳолда нечта солиштиришлар бажарилишини қараймиз. Биринчи ўтишдан сўнгги тўхташда солиштиришлар сони N – 1 га тенг. Икки ўтишдан сўнг солиштиришлар сони N - 1 + N – 2 га тнг бўлади. C(i) билан биринчи i ўтишда бажарилган солиштиришларни белгилаймиз. Мадомики, агар ҳеч қандай алмаштириш бажарилмаса алгоритм ўз ишини якунлайди ва биз ўртача ҳол таҳлилида бу имкониятларни барчасини қараш керак. Натижада қуйидаги тенгликка келамиз



бунда, С(i) – for циклидаги биринчи i ўтишдаги солиштиришлар сонига тенгва у қуйидагича



(охирги тенглик (1.10) тенгликдан келиб чиқади), ёки


Охирги тенгликни A(N) ифодага қўйиб, ҳосил қиламиз



N– i дан боғлиқ эмас, (1.11) ва (1.14) тенгликлар беради



(1.11) дан яна фойдаланиб ва элементар алгебрани қўллаб қуйидагини ҳосил қиламиз



Ниҳоят, (1.15) ва (1.16) тенгликлар беради