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

2.2.1. Ўрнига қўйиш усули билан саралаш алгоритми
Қўйиш усулининг асосий ғояси қарийб сараланган рўйхатга янги элементни қўшишда у ихтиёрий жойидан керакли жойга қўйиш ва рўйхатни қайта саралашдир. Бунда дастлабки рўйхатнинг биринчи элементидан бир элементли сараланган рўйхат тузилади. Кейин дастлабки рўйхатнинг иккинчи элементи сараланган бир элементли рўйхатнинг тегишли жойига қўйилади ва натижада икки элементли сараланган рўйхат ҳосил бўлади. Энди дастлабки рўйхатнинг учинчи элементини сараланган икки элементли рўйхатнинг керакли жойига қўйиш мумкин. Бу жараён то дастлабки рўйхатнинг барча элементлари ушбу рўйхатнинг сараланган қисмида жойлашгунча давом эттирилади.
Ушбу жараённи амалга оширувчи алгоритм қуйидагича:
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 ўзгарувчига таъминлайди. Кейин массивдаги барча катта элементлар бир ўринга силжиб ушбу янги элементга жой ажратилади. Циклнинг охирги итерацияси location+1 рақамли элементни location+2 ўринга кўчиради. Бу шуни билдирадики location+1 ўрин «янги» элемент учун бўшатилади.
Энг ёмон ҳолат таҳлили
Агар ички while циклига қарасак кўриш мумкинки, агар ҳар сафар янги қўшиладиган элемент сараланган қисм барча элементларидан кичик бўлса, у ҳолда энг кўп амаллар бажарилади. Бу ҳолда цикл иши location ўзгарувчи 0 га тенг бўлганда тўхтайди. Шунинг учун алгоритм энг кўп ишни янги элементни рўйхат бошига қўйганда бажаради. Бу ҳолат берилган рўйхат камайиш тартибида сараланган ҳолда юз беради ва бу энг ёмон ҳол ҳисобланади.
Ушбу ҳолдаги жараённи кўрамиз. Биринчи ўринга рўйхатнинг иккинчи элементи қўйилади. У атиги битта элемент билан солиштирилади. Иккинчи қўйиладиган элемент (тартиб бўйича учинчи) олдинги иккитаси билан солиштирилади, учинчи қўйиладиган элемент эса олдинги уч элемент билан; умуман, i- қўйиладиган элемент олдинги i та элемент билан солиштирилади ва бу жараён N-1 марта бажарилади. Шу туфайли қўйиш усули билан саралашнинг энг ёмон ҳолдаги қийинлиги қуйидагига тенг