Piramidali Tartiblash buxoro davlat universiteti fizika-matematika fakulteti

1.3 – listing. Piramidali tartiblash protsedurasi.
{A[1] …A[n] massiv elementlarini kamayish tartibida xilga ajratadi }
var i ;integer
{A massivida kursor}
begin
{qisman tartiblashtirilgan daraxtni yaratish}

{to’dadan minimal elementni yo’q qilish}

{Qisman tartiblashtirilgan daraxtni tikash}
end
end; (heapsort)

Piramidali tartiblash abstrakt shaklining tahlili
Avvalo pushdovn pratsedurasining bajarish vaqtini baholaymiz While davrining qismi(yani bu davirning alohida interatsiyasi)
Hisobga olingan vaqtda bajariladi har bir interatsiyadan kiyin uzgaruvchi r hech bo’lmaganda o’z ahamiyatini ikki baravar kupaytiradi .shuning uchun r ning boshlang’ch ahamiyati first gat eng, I interatsiyadan kiyin r>=firs*2i.lost/2 tengsizligi bajarilsa bu shart bajariladi
(1)
Oxirgi tengsizlikni shunday kuchirish mumkun:
Binobarin ,pushdown protsedurasida while davri iteratsiyalar soni log(last/first) dan oshmaydi.
Chunonchi, first 1 va last n, unda (1) dan O(log n) dan ko’ra katta bo’lmagan tartib bo’yicha 1.3 listingning (2) va (5) satrlarda pushdown protsedurasining har bir chaqiruviga vaqt sarf qilinardi. Aftidan, (1), (2) satrlarning for sikli n/2 marta bajariladi. Shuning uchun bu sikl bajarilishining umumiy vaqti O(n log n) tartibga egadir. (3) va (5) satrlarda davr n-1 marta bajariladi. Binobarin, hamma joyda almashtirishni bajarishga (4) satrda O(n) tartibining vaqti sarf qilinadi, qisman tartiblangan daraxtning tiklashiga (5) satrda O(n log n). Shu yerdan kelib chiqadiki, (3)-(5) satirlarda davrini bajarishning umumiy vaqti O(nlogn) tartibga ega va shunday .

Xulosa
Heapsort mualajasi eng yomon vaziyatda O(nlogn) tartibning bajarish vaqtiga ega, o’rtacha uning tez xilga ajratishdan ko’ra vaqti ancha yomonroq ush tartibga ega bo’lsa ham Piramidali tartiblash nazariy rejada qiziqdir chunonchi bu O(nlogn) bajarish vaqti eng yomon vaziyatda ega bo’lgan biz tomondan birinchi ko’rib chiqilgan algoritimdir. Amaliy vaziyatlarda bu algoritim ruyxatining ajralishi emas balki faqat eng kichik k elimentlarni tanlab olish kerak bo’lganda foydalidir , shunda k da esa n ancha kam . oxirgi xulosada (1),(2) satirlarda haqiqatda davirning bajarish vaqti O(n) tartibga egadir. Agar (3)-(5) davirning faqat k itiratsiyasiyalarini qilish kerak bo’lsa , undaO(klogn) tartibning vaqti shunga sarf qilinadi .Shu uchun minimal elimentlarning k tanlovi heapsort pratsedura O(n+klogn) tartibida bajaradi. Shu erdan kelib chiqadiki, k<=n/logn dab u operatsiya bajariladi O(n) tartibda vaqt talab qilinadi.