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

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