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:
( )
( ) ( )
( )
(
)
Do'stlaringiz bilan baham: |