10-Amaliy ish Graflar bilan ishlovchi soda algoritmlar

 
 
 
 
O„rtacha holat tahlili
Eng yomon holatda For sikli N – 1marta takrorlanishini ko„rdik. O„rtacha holatda almashtirishsiz 
o„tishlarning bajarilish ehtimoli barcha N - 1 ta o„tish uchun teng deb hisoblayiz.Har bir
o„tishda nechta taqqoslash bajarilishini ko„raylik.Birinchi o„tishdan keyingi to„xtashdan keyin 
taqqoslashlar soni N – 1 ga teng.Ikkita o„tishdan keyin taqqoslashlar soni N - 1 + N – 2 ga teng.
S(i) bilan birinchi i ta o„tishdan jarayonida bajarilgan taqqoslashlar sonini belgilaymiz. Natijada 
quyidagi tenglikka ega bo„lamiz: 
( )
∑ ( )
Buyerda 
(
) For siklining 1- i ta o„tishi davomidagi taqqoslashlar soniga teng. S (i) ning 
qiymati quyidagiga teng: 
( )
( ) 
( ) 
 
Bu ifodani 
( )
ni formulasiga qo„ysak, quyidagiga ega bo„laiz: 
 
( )
∑
Ushbu forula ba‟zi alebraik shakl almashtirishlardan keyin quyidagi ko„rinishni oladi: 
( )
( 
)
Piramidali saralash algoritmi
Piramidali saralash algoritmining asosida binar daraxtning piramida deb ataluvchi maxsus 
turidan foydalanish yotadi. Bunday binar daraxt tugunlarining qiymati eng
yaqin avlodlari qiymatidan doimo katta bo„ladi.Saralash jarayoni piramida qurilishidan 
boshlanadi. Bunda ro„yxatning aksimal elementi daraxtning eng yuqori tugunida joylashadi. 
So„ngra ushbu element ro„yxatning yeng oxirgi navbatiga joylashtiriladi.Elementi olingan 
piramida esa qaytadan quriladi.Natijada daraxt ildizida kattalik bo„yicha ikkinchi o„rinda 
turadigan element joylashadi va uni ro„yxatning oxiridan bitta oldingi o„ringa 

---

o„tkaziladi.Protsedura barcha elementlar ro„yxatdagi o„z o„rinlarini egallagunlaricha davom 
etadi.Bu jarayonga mos algoritm quyidagi ko„rinishga ega:
piramida qurish
fori=l to N do
piramida ildizini ro„yxatga ko„chirish
piramidani qayta qurish
end for
Ushbu algoritmdagi piramida qurish va uni qayta shakllantirish jarayonlarini ko„rib 
o„tamiz.Bu jarayonlar algoritm effektivligiga ta‟sir ko„rsatadi. Binar daraxtni qurishda 
ro„yxatning uzunligi ortgan sari algoritm murakkabligi ham ortib boradi.Piramida qurishda 
quyidagi mulohazalardan kelib chiqish mumkin: Ro„yxatning i-elementi eng yaqin avlodlarining 
2i va 2i +1 pozitsiyalardan yozamiz. Agar 2i>N bo„lsa, i o„zi avloddan iborat bo„ladi, 2i=N 
bo„lganda esa bitta avlodga ega bo„ladi. 1-rasmda piramida va uning ro„yxat ko„rinishlari 
ifodalangan:
Piramidani qayta qurish
Piramidaning ildizi ro„yxatga ko„chirilganda, ildiz element bo„sh qoladi. Uning joyiga avlod 
elementlaridan kattasi joylashtirilishi kerak. Piramidani qayta shakllantirish jarayoni eng quyi 
darajaning o„ngdan birinchi elementidan boshlanadi. Natijada piramida quyi darajasidagi 
elementlar bir tekis yo„qotib boriladi: 
Piramida(list,root,key,bound) 
list saralanuvchi ro‟yxat 
root piramida ildizi nomeri 
key piramidaga koritiluvchi kalit qiymat 
bound piramidaning o‟ng chegarasi(nomer) 
vacant=root 
while 2*vacant<=bound do 
largerChild=2*vacant 
//enf yaqin avlod elementlardan kattasini tanlash 
If (largerChild list[largerChild+1]) then 
largerChild= largerChild+1 
end if 
//Kalit joriy avlod elementdan yuqoridami? 
If key> list[largerChild] then
// Ha, sikl to‟xtatiladi 
break 
else // Yo‟q, kattaroq eng yaqin avlodni ko‟tarish kerak 
list[vacant]= list[largerChild] 
vacant= largerChild 

---

end if 
end while 
list[vacant]=key 
Bu yerda root o„zgaruvchisining vazifasi nimada?, degan savol tug„iladi. Ushbu qo„shimcha 
parametr piramidani pastdan yuqoriga qurish imkonini beradi. 
Piramidani qurish 
Piramida funksiyasining tuzilishi piramidaning boshlan g„ich holatini shakllantirish 
imkonini beradi. Ikki ixtiyoriy qiymatni bo„sh avlodlar deb hisoblab, ulardan kichik piramidalar 
quriladi.So„ngra ular ketma-ket ro„yxatga yig„iladi. Ushbu quyida keltirilgan sikl bu prsedurani 
realizatsiya qiladi: 
For i=N/2 down to 1 do 
Piramida(list,I,list[i],N) 
End for 
Endi piramida elementlarini ro„yxatga o„tkazish protseduralarini qo„shib, quyidagi to„liq 
algoritmga kelamiz: 
for i=N/2 down to 1 do 
Piramida(list,i,list[i],N) 
end for 
For i=N down to2 do 
max=list[1] 
Piramida(list,i,list[i],i-1) 
list[1]=max 
end for 
MergeLists algoritmining tahlili 
MergeLists protsedurasi elementlarni taqqoslash vazifasini bajaradi. A ro„yxatning barcha 
elementlari V ro„yxatning barcha elementlaridan kichik bo„lgan holni ko„ramiz. Bunda A[1] va 
V[1] eleyentlar taqqoslanadi va A[1] element kichik bo„lganligi uchun S ga joylashtiriladi. 
So„ngra V[1] va A[2] elementlar taqqoslanib, A[2] element S ga joylashtiriladi.A ro„yxat 
yelementlarining V[1] bilan taqqoslanishlar soni NA A ro„yxat elementlari soniga teng bo„ladi. 
Aks holda, agar V ro„yxatning barcha elementlari A ro„yxat elementlaridan kichik bo„lsa, 
taqqoslashlar soni NV V ro„yxat elementlari soniga teng bo„ladi. A ro„yxatning 1-elementi V 
ro„yxat 1-elementidan katta bo„lib, A ro„yxatning barcha elementlari V ro„yxatning 2-
elementidan kichik bo„lganda A[1] va V[1] taqqoslanib, V[1] S ro„yxatga o„tkaziladi.So„ngra A 
ro„yxatning qolgan yelementlari V[2] bilan taqqoslanib, ketma-ket S ga o„tkaziladi. Bunda 
taqqoslashlarning to„liq soni NA + 1 ga teng bo„ladi. Bundan birinchi situatsiyaning(A 
ro„yxatning barcha elementlari V ro„yxatning barcha elementlaridan kichik) eng yaxshi holat 
ekanligi kelib chiqadi. Quyidagi situatsiya ushbu algoritm uchun yeng yomon holat bo„lib 
hisoblanadi: A[1] element V[1] va V[2] orasida, A[2] element V[2] va V[3] orasida, A[3]
element V[3] va V[4] orasida bo„ladi va hokazo. Bunda S ro„yxatga ko„chirib o„tkazish har 
ikkala ro„yxatdan navbat bilan amalga oshiriladi. Bunda har ikkala ro„yxat elementlari uchun NA
va NV ga teng taqqoslashlar amalga oshirilganligi uchun eng yomon holat uchun algoritm 
murakkabligi NA+ NV-1 ga teng bo„ladi. 
MergeSort algoritmining tahlili 
Ushbu funksiya first o„zgaruvchisining qiymati last o„zgaruvchisining qiymatidan kichik 
bo„lgan holda chaqiriladi. Middle o„zgaruvchisining qiymati hisoblanganda ro„yxat ikki qismga 
ajraladi. Middle o„zgaruvchisining qiymati first va last o„zgaruvchilari qiymatlarining o„rtasida 
joylashganligi uchun ro„yxat ikki teng qsmga ajraladi.Har bir qism ro„yxat N/2 ta elementdan 
iborat bo„ladi. Bunda MergeLsits algoritmning tahliliga ko„ra, birlashishi jarayonida eng yaxshi 
holatda N/2 ta, eng yomon holatda N/2 + N/2 -1- N-1 ta taqqoslash amali bajariladi. Bundan 

---

birlashtirish bilan saralash algoritmining murakkabligi eng yaxshi va eng yomon holatlar uchun 
bir xilda W(N)=B(N)=O 
Log
2
N ekanligini keltirib chiqarish mumkin. 
Tez saralash algoritmi 
Tez saralash yana bitta rekursiv algoritmdir.Uning ma‟nosi quyidagicha: ro„yxatdan biror 
elementni tanlab, algoritm uning yordamida ro„yxatni ikki qismga ajratadi. Birinchi qism 
ro„yxatga ushbu elementdan kichik qiymatlar, ikkinchisiga ushbu elementdan kattalari 
joylashtiriladi. Keyingi qadamda ushbu ikki qism ro„yxat xuddi shu usul bilan yana ikki qismga 
ajratiladi va hokazo. 
Eng yomon holat tahlili 
PivotList protsedurasi N elementdan iborat ro„yxat uchun chaqirilganda , u N – 1 ta 
tqqoslash amalini bajaradi, chunki PivotValue ning qiymati ro„yxatning qolgan barcha 
eleyentlari bilan taqqoslanadi.Eng yaxshi holatda PivotList ro„yxatni teng uzunlikdagi ikki 
bo„lakka ajratadi.Eng yomon holatda esa ushbu bo„laklar uzunligi bir-biridan maksimal darajada 
farq qilishi kerak. Bunga PivotValue qiymati ro„yxatning qolgan barcha elementlaridan katta 
yoki kichik bo„lganda erishish mumkin.Bunda ro„yxatlarning birida bitta ham element 
bo„lmaydi, ikkinchisi esa N - 1 elementdan tashkil topadi. Agar har bir rekursiv murojaatda 
bunday holat yuz beradigan bo„lsa, har safar bitta elementga kamayish(PivotValue) yuz beradi.
Bundan taqqoslashlar soni quyidagi formula bilan topiladi degan xulosaga kelamiz:
=
=1 
−1=
(
−1)2 
Bunday tatijani elementlarning qanday tartibi berishi mumkin? Agar har bir o„tishda 
birinchi element tanlansa, ushbu element eng kichik yoki eng katta bo„lishi kerak. Demak, 
saralangan boshlang„ich ro„yxat eng yomon holatni berar ekan. 
O„rtacha holat tahlili 
Bizga N elementdan iborat ro„yxat berilgan bo„lsin. Faraz qilaylik PivotValue ning qiymati 
ro„yxatning qolgan barcha elementlari qiymatidan katta bo„lsin. Bu protsedura oxirida PivotPoint 
ning qiymati N ga teng ekanligini bildiradi.Shuning uchun PivotValue o„zgaruvchisi ro„yxatning 
birinchi emas, oxirgi elementini ko„rsatadi.Ro„yxatning oxirgi elementi uning qiymati bo„yicha 
eng kichigi ham bo„lishi mumkin. Shuning uchun ushbu ikki qiymatlarning o„rin almashishi 
ro„yxatning eng katta elementni birinchi pozitsiyadan oxirgi pozitsiyaga, eng kichigini esa 
oxirgidan birinchi pozitsiyaga o„tkazadi. Agar eng katta element birinchi tursa, u ro„yxatning 
qolgan elementlari bilan N - 1 ta inversiyani tashkil etadi. Xuddi shunday oxirida turgan eng 
kichik element qolgan elementlar bilan N - 1 inversiyani tashkil etadi. Shunday qilib, ikkita 
chekka elementning o„rnini almashtirish 2N - 2 ta inversiyani yo„qotadi. Shuning uchun tez 
saralash algoritmining o„rtacha holatdagi murakkabligi eng yomon holatdagisidan farq qiladi.
Algoritm ishida asosiy vazifani PivotList prsedurasi bajarganligi uchun uning ishini tahlil 
qilamiz. PivotList algoritmi bajarilgandan keyin N ta pozitsiyadan ixtiyoriysi PivotValue ni 
o„zida saqlashi mumkin. Eng yomon holat tahlilida PivotList protsedurasi N elementdan iborat 
ro„yxatni bo„laklarga bo„lib, N – 1 ta taqqoslash amalini bajarishini ko„rdik.Ushbu ro„yxatlarni 
birlashtirish hech qanday xarakatni talab etmaydi. PivotList protsedurasi R qiymatni berganda
R – 1 va N – R uzunlikdagi ro„yxatlar uchun Quicksort protsedurasiga murojaat yuz beradi. 
O„rtacha holat tahlilida R ning barcha mumkin bo„lgan
N ta qiymatlari hisobga olinishi kerak. Bularga asoslanib quyidagi rekkurent munosabatga 
kelamiz: 
( ) ( )
(∑ ( ) ( )))
)
Ushbu ifodada ba‟zi shakl almashtirishlar qilingandan keyin quyidagi soddalashgan ko„rinishga 
keladi: 

---

 ( )
( ) ( )
( )
(
)