Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

2–маъруза: Қўшилган саралаш. Қўшилган саралаш корректлиги. Псевдокод тузишда келишув. Алгоритм таҳлили.
Режа:

1. 
   Қўшилган саралаш;
   
2. 
   Қўшилган саралаш корректлиги;
   
3. 
   Псевдокод тузишда келишув;
   
4. 
   Алгоритм таҳлили;
   

Қўшимчалар билан саралаш
Қўшимчалар билан саралашнинг асосий ғояси шундаки, янги элементни сараланган рўйхатга қўшишда уни ихтиёрий жойга эмас, балки керакли жойга жойлаштириш лозим, сўнг бутун рўйхатни бошқатдан саралаш керак. Қўшимчалар билан саралашда ихтиёрий рўйхатнинг биринчи элементи сараланган рўйхатнинг 1 узунлиги деб ҳисобланади. 2 элементли сараланган рўйхат бошланғич рўйхатдаги 2-элементни 1-элемент жойлашган рўйхатнинг керакли ўрнига жойлаштириш орқали яратилади. Энди бошланғич рўйхатнинг 3-элементини сараланган 2 элементли рўйхатга қўйиш мумкин. Бу жараён бошланғич рўйхатнинг барча элементлари кенгаювчи сараланган рўйхатга жойлашгунга қадар давом этади.
Бу жараённи ифодаловчи алгоритм қуйида келтирилган:
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 ўзгарувчисига юклайди. Сўнг барча катта элементларни 1 позицияга суриб, бу элементга жой ажратади. Циклнинг охирги итерацияси элементни location+1 номер билан location+2 позиция ўтказади.


Энг ёмон ҳолат таҳлили
Агар ички while сиклини кўриб чиқадиган бўлсак, яна бошқатдан қўшилаётган элемент барча элементларда кичик ва рўйхатнинг сараланган қисмида жойлашган бўлса, жараённинг катта қисми бажарилади. Бу ҳолатда location ўзгарувчисининг қиймати 0 га тенг бўлганда цикл тўхтайди. Шунинг учун алгоритм бажарилишининг асосий қисми ҳар бир янги элемент рўйхат бошига қўшилганда амалга оширилади. Бу фақатгина бошланғич рўйхат элементлари камайиш тартибда бўлганда бажарилади. Бу энг ёмон ҳодисалардан бири, лекин бошқалари ҳам бор.
Бундай рўйхатни қайта ишлашни қандай амалга ошириш кераклигини кўриб чиқамиз. Дастлаб рўйхатнинг 2-елементи қўйилади. У фақатгина битта элемент билан таққосланади. Иккинчи қўйилган элемент олдинги иккита элемент билан, учинчи қўйиладиган элемент учта элемент билан ва ҳоказо, i-қўйиладиган элемент i та элемент билан таққосланади ҳамда бу жараён N-1 марта такрорланади. Шундай қилиб, энг ёмон ҳолатдаги саралаш мураккаблиги қуйидагига тенг: