Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Яхши ҳолат таҳлили
SwappedElements байроқ изоҳи нотўғри эканлигини таъкидлаш учун яхши ҳолат таҳлилини қисқача кўриб чиқамиз. Бажарилаётган иш ҳажми қайси ҳолатда минимал бўлишини кўриб чиқамиз. For сикли 1-ўтишда тўлиқ бажарилиши керак ва шунинг учун алгоритмга камида N-1 та таққослаш талаб этилади. 2 та имкониятни кўриб чиқиш керак: 1-ўтишда ҳеч бўлмаганда битта ўрин алмаштириш ёки ўрин алмаштириш бажарилмайди. 1-ҳолатда ўрин алмаштириш SwappedElements байроғининг қиймати true га ўзгаришига олиб келади, демак while цикли яна такрорланади, бунда N-2 та таққослаш талаб этилади. 2-ҳолатда SwappedElements элемент байроғи false қийматини сақлаб қолади ва алгоритм бажарилиши тўхтатилади.
Шунинг учун яхши ҳолда N-1 та таққослаш бажарилади, бунда 1-ўтишда ўрин алмаштиришлар бўлмайди. Бундан эса маълумотларнинг яхши тўплами талаб қилинган тартибда элементлар рўйхатини ташкил этиши келиб чиқади.
Ёмон ҳолат таҳлили
Яхши ҳолда рўйхатдаги элементлар талаб қилинган тарибда жойлашар экан, элементларнинг тескари тартибда жойлашиши ёмон ҳолни бермасмикан, деган савол туғилади. Агар энг катта элемент 1-ўринда турса, у ҳолда у рўйхат охиригача қолган барча элементлар билан ёнма-ён қўйиб борилади.1-ўтишдан олдин катта қийматдаги 2-елемент 2-ҳолатни эгаллайди, бироқ 1-таққослаш ва 1-ўрин алмаштириш натижасида у 1-ўринга ўтказилади. 2-ўтишнинг бошида 1-ҳолатда катта қийматдаги 2-елемент жойлашган бўлади ва у рўйхатнинг охиридан 2-елементгача қолган элементлар билан ёнма-ён ўрин алмашиб боради. Бу жараён барча қолган элементлар учун бажарилади, шунинг учун for цикли N-1 марта такрорланади. Шунинг учун берилганларнинг тескари тартиби ёмон ҳолга олиб келади.
Ёмон ҳолда нечта таққослаш амалга оширилади? 1-ўтишда қўшни элементларнинг N-1 та таққослаши, 2-ўтишда эса N-2 та таққослаш бажарилади. Тадқиқотлар шуни кўрсатадики, ҳар бир навбатдаги ўтишда таққослашлар сони биттага камаяди. Шунинг учун ёмон ҳол мураккаблиги қуйидаги формула билан берилади: