Amaliy matematika va informatika” yo’nalishi 19. 08 a-guruh talabasi Eshimova Gulsumoyning

6-rasm. Merge sort (qo'shib saralash ) algoritmi diogrammasi.

* Heap sort( piramidasimon saralash) bu Binary Heap ma'lumotlar tuzilishiga asoslangan taqqoslashga asoslangan tartiblash texnikasi. Bu birinchi navbatda minimal elementni topadigan va minimal elementni boshiga qo'yadigan tanlov tartibiga o'xshaydi. Qolgan elementlar uchun xuddi shu jarayonni takrorlaymiz.

7-ras m. Heap sort ( piramidasimon saralash) algoritmi diogrammasi.

1.4 PIIRAMIDASIMON SARALASHNING MAZMUN MOHIYATI.

Kompyuter fanida piramidal saralash bu saralash algoritmiga asoslangan taqqoslashdir. Piramidal saralashni yaxshilangan tanlov turi deb hisoblash mumkin: ushbu algoritm singari, u oz hissasini saralangan va saralanmagan mintaqaga ajratadi va eng katta elementni ajratib olish va bu saralangan mintaqada harakat qilish uchun yolning ajratilmagan qismini qisqartiradi. Yaxshilanish maksimal qiymatni topish uchun chiziqli vaqtni qidirishdan kora, malumotlarning strukturasini pasaytirishdan iborat. Amalga oshirilgan saralashga qaraganda aksariyat mashinalarda sekinroq bolsa-da, eng yaxshi O(nlogn) bajarilishining afzalligi bor. Piramidal turlarga ajratish algoritmi mavjud, ammo bu turgun emas. Piramidal turlarga ajratish 1964 yilda JWJ Uilyams tomonidan ixtiro qilingan. Uilyams allaqachon foydali malumotlar tuzilmasi sifatida oz ixtiyorida bolgan. Xuddi shu yili RW Floyd Treesort algoritmida oldingi izlanishlarni davom ettirib, qatorni joyiga qoyishi mumkin bolgan takomillashtirilgan versiyasini nashr etdi.

Pirаmidаli sаrаlаsh Dj.Uilyamе tоmоnidаn tаklif еtilgаn vа R.Flоyt tоmоnidаn rivоjlаntirilgаn. Bundа S mаssiv D binаr dаrахt ko’rinishidа ifоdаlаnаdi vа qo’shimchа хоtirа tаlаb еtmаydi. Аlgоritmning bаjаrilish murаkkаbligi О (n log2n) gа tеng.

S(l), S(2), ..., S(n) (5) mаssiv bеrilgаn bo’lsin. (5) еlеmеntlаrning

S(p),S(p+l),..., S(q) (l

Ko’rinishdаgi kеtmа-kеtlik pirаmidа dеb аtаlаdi, qаchоnki quyidаgi shаrtlаrdаn biri bаjаrilsа:

1) 2p>q

2) lp=q,S(p)>S(q)

3)2pS(2j)

(p

Tа’rifdаn quyidаgilаr kеlib chiqаdi:

1) Iхtiyoriy (5) kеtmа-kеtlik uchun S(n/2+l), S(n/2+2),...,S(n) kеtmа-kеtlik pirаmidа bo’lib hisоblаnаdi;2) Аgаr (5) kеtmа-kеtlik pirаmidа bo’lsа, u hоldа S(l) >max S(j) (7) 3) Аgаr (5) kеtmа-kеtlik pirаmidа bulib, binаr D dаrахt kurinishidа bеrilgаn bo’lsа, D dаgi iхtiyoriy tugunning qiymаti uning chаp vа o’ng аvlоdlаri qiymаtidаn kichik bo’lmаydi. 2-Misоl. 90, 70, 11, 8, 3, 9, 7, 5, 6, 1, 2 kеtmа-kеtlik bеrilgаn vа u pirаmidаdir:90 70 11 8 3 9 7 5 6 12 Pirаmidаli sаrаlаsh ikki еtаpdаn ibоrаt bulаdi: 1-еtаp. Pirаmidаni qurish. (5) kеtmа-kеtlikdа. S(n/2+l), S(n/2+2),...,S(n) (8)Pirаmidаdir. (8) kеtmа-kеtlikkа (5) dаn qоlgаn еlеmеntlаrni qo’shаmiz.

S(j+1), S(j+2),...,S(n) pirаmidа bo’lsin. Chаpdаn S(j) еlеmеntni qo’shib,

S(a), S(j+l),S(j+2),...,S(n) (9)

(9) ni yanа pirаmidаgа аylаntirаymiz, ya’ni S(j) vа uning ikkitа аvlоdi S(2j) vа S(2j+1) lаr tеkshirilаdi. Bundа аgаr S(j) аvlоdlаridаn kichik bo’lmаsа hisоblаshlаr to’хtаtilаdi, chunki (9) pirаmidа bo’lib hisоblаnаdi. Аks hоldа S(j) vа max(S(2j), S(2j+1)) qiymаtlаrni аlmаshtirаmiz vа h.k.z. Охiridа (5) pirаmidgа аylаnаdi vа (7) bаjаrilаdi. Оlingаn S pirаmidаni jоriy dеb е’lоn qilаmiz vа 2-еtаpgа o’tаmiz. 2-еtаp. Jоriy S pirаmidаdа 1-еlеmеnt qоlgаnlаridаn kichik еmаs. S ning chеkkа еlеmеntlаri qiymаtlаrini o’zаrо аlmаshtirib, S ni ung tоmоndаn bittаgа qisqаrtirаmiz. Hоsil bo’lgаn kеtmа-kеtlik pirаmidа bo’lmаsligi hаm mumkin. S(1) еlеmеnt uchun 1-еtаpdаgi jаrаyonni qo’llаb, o’zgаrtirilgаn S kеtmа-kеtlik yanа pirаmidаgа аylаntirilаdi. 2-еtаpni p-1 mаrаtа bаjаrib, Sni o’smаslik tаrtibidа sаrаlаb оlаmiz.

Piramidal saralash algoritmini ikki qismga bolish mumkin.

Birinchi bosqichda toplangan malumotlar malumotlar asosida quriladi. Uyumlar kopincha toliq ikkilik daraxti joylashgan qatorga joylashtiriladi. Toliq ikkilik daraxti ikkilik daraxtning tuzilishini massiv indekslariga moslashtiradi; har bir qator indeksi - bu tugun; ota-ona tugunining korsatkichi, bolaning chap bolagi yoki bolaning ong filiali oddiy iboralardir. Nolga teng ravishda massivni olish uchun ildiz tugmasi 0 indeksida saqlanadi.

Ikkinchi bosqichda, eng katta elementni bir necha marotaba toplash (toplanganning ildizi) dan olib tashlab, massivga joylashtirilgan tartiblangan massiv yaratiladi. Topni yigish xususiyatini saqlab qolish uchun har bir ochirishdan keyin uyum yangilanadi. Toplamdan barcha obektlar olib tashlanganidan song, natija berilgan qator piramidal tartiblash joyida amalga oshirilishi mumkin. Massivni ikki qismga ajratish mumkin, tartiblangan qator va shamlardan. Saqlash chiqindilari massivlar sifatida korsatilgan. Toplangan invariant har bir qazib olishdan keyin saqlanib qoladi, shuning uchun qazib olishning narxi shundan iborat.

Piramidal turlarga ajratish algoritmi birinchi bolib royxatni maksimal yigishga aylantirishni tayyorlashni oz ichiga oladi. Keyinchalik algoritm royxatning birinchi qiymatini oxirgi qiymat bilan bir necha marta almashtiradi, toplash jarayonida korib chiqilgan qiymatlar oraligini birma-bir qisqartiradi va yangi birinchi qiymatni uyumdagi holatga otkazadi. Korib chiqilgan qiymatlar oraligi bitta uzunlik qiymatiga teng bolgunga qadar takrorlanadi.

Piramidal turlarga ajratish

Pastdan yuqoriga qarab, piramidal tartiblash muhim omil tomonidan talab qilinadigan taqqoslash sonini kamaytiradigan tanlovdir. Ananaviy piramidal turlarga ajratish eng yomon holatlar uchun 2nlog(2)[n] + O (N) taqqoslashni talab qiladi va ortacha, yuqoridan yuqoriga variant uchun nlog(2)[n] + O (1) taqqoslashni talab qiladi va ortacha 1,5 L log(2)[n] + O (n).

Bunga siftDown protsedurasini takomillashtirish orqali erishiladi. Ozgarish chiziqli vaqtni yigish bosqichini biroz yaxshilaydi, ammo ikkinchi bosqichda ahamiyatliroq boladi. Oddiy piramidal tartiblash singari, ikkinchi bosqichning har bir iteratsiyasi topning yuqori qismini egallaydi [0] va u qoldirgan boshliqni [oxirida] toldiradi va songra ushbu oxirgi elementni uyum ostiga oladi. Ammo bu element uyumning eng past darajasidan kelib chiqadi, yani u uyumdagi eng kichik elementlardan biridir, shuning uchun uni pastga siljitish, ehtimol uni orqaga qaytarish uchun kop harakatlarni talab qiladi. Ananaviy piramidal turlarga ajratishda har bir elakdan voz kechish kamida uchta elementni topish uchun ikkita taqqoslashni talab qiladi: yangi tugun va uning ikkita bolasi.

Piramidal tur pastdan yuqoriga qarab, har bir darajaga bittagina taqqoslash yordamida katta bargli daraxtlarning barglari darajasida (goyo kiritilgan). Boshqacha qilib aytganda, u ozi va barcha ota-bobolari akalari va singillaridan kattaroq yoki teng keladigan mulkka ega bolgan bargni topadi. (Agar bir xil kalitlar bolmasa, bu varaq noyobdir.) Keyin ushbu varaqdan [oxirida] qoyish uchun ushbu yoldagi togri joylashishni qidiradi. Bu odatiy piramidal saralash topilmalari bilan bir xil va joylashishni amalga oshirish uchun bir xil miqdordagi almashinuvlarni talab qiladi, ammo bu joyni topish uchun kamroq taqqoslash talab etiladi.

Pastki qismdan yuqoriga qarab, piramidal saralash the16000 olchovli massivlarda (medianani tezda saralash orqali uch saralash orqali) urish elon qilindi.

2008 yilda ushbu algoritmni qayta baholash shuni korsatdiki, bu butun sonlar uchun odatiy piramidal tartiblashdan tezroq bolmaydi, chunki zamonaviy filial bashoratlari pastdan yuqoriga qarab oldini olish mumkin bolgan bashorat qilinadigan taqqoslash narxini bekor qiladi.

Uch tomonlama piramidal tur ikkilik toda orniga uch komponentli uyumdan foydalanadi; yani uyadagi har bir elementning uchta bolasi bor. Dastur bilan ishlash yanada qiyinlashadi, lekin doimiy almashtirishni va operatsiyalarni taqqoslashni bir necha bor kamaytiradi. Buning sababi shundaki, uch baravar ortilgan past qadamda uchta taqqoslash va bitta almashtirish talab etiladi, ikkilik uyumda esa ikkita taqqoslash va bitta almashtirish talab qilinmaydi. Uch darajali uyumdagi ikki daraja 3^ 2 = 9 elementni oz ichiga oladi, ikkitadan yigindagi uchta darajani bir xil miqdordagi taqqoslash bilan koproq ishlang, bu faqat 2^ 3 = 8 ni qamrab oladi, bu birinchi navbatda akademik qiziqish uygotadi, chunki qoshimcha murakkablik ozgina tejashga loyiq emas. , va pastdan yuqoriga qarab, piramidal tartiblash ikkalasini ham yengadi.

Togri tartiblash algoritmi 1981 yilda Edsger Dijkstroy tomonidan ishlab chiqilgan piramidal saralashning bir turi. Piramidal saralash sifatida, Silliq tartiblash O (n n ning n yuqori chegarasi) dir. Smooth Sorting-ning afzalligi shundaki, agar kirish allaqachon malum darajada tartiblangan bolsa, u O (n) vaqtga yaqinlashadi, boshlangich holatidan qati nazar O (n kiritish n) ortacha piramidal navi. Murakkabligi tufayli Smooth Sort kamdan kam ishlatiladi. Levcopoulos va Peterson, piramidal turlarning ozgarishini Karteziya daraxtlarining toplanishi asosida tasvirlaydi. Birinchidan, {{matematik | ga kirish joyidan Cartesian daraxti qurilgan O (n) vaqt va uning ildizi 1 elementli ikkilik uyumga joylashtirilgan. Keyin biz ikkilik uyumdan minimal miqdorni, ildiz elementi daraxtining hosilasini chiqarib tashlaymiz, shuningdek, ikkitomonlama uyumda ozlari ham karteziya daraxtlari bolgan chap va ong bolalarni (agar mavjud bolsa) qoshamiz. Ular korsatib turibdiki, agar kirish allaqachon saralangan bolsa, Cartesian daraxtlari juda muvozanatsiz boladi, bir nechta tugunlar bolalar huquqlarini qoldiradi, buning natijasida ikkilik uyum kichik bolib qoladi va algoritmni kirish uchun O (n log n) dan tezroq saralashga imkon beradi, deyarli tartiblangan.

Zaif piramidal tartiblash kabi bir nechta variant, har bir tugun uchun bitta qoshimcha status bitidan foydalanib, nazariy minimumga yaqin bolgan nlоgа ₂ n + O (1) taqqoslashni talab qiladi. Ushbu qoshimcha bit algoritmlarni ishdan chiqaradi, agar siz elementning ichida joy topa olsangiz, bu algoritmlar sodda va samarali, ammo agar kalitlarni taqqoslash yetarli darajada arzon bolsa (masalan, butun tugmalar) ikkilamchi toplanishlarga qaraganda sekinroq) shundan kelib chiqadiki, doimiy omil muhim emas.

Piramidal saralash birinchi navbatda tez saralash bilan raqobatlashadi, saralash algoritmiga asoslangan boshqa juda samarali umumiy maqsad - deyarli joyida taqqoslash. Kviksort odatda bazi omillar tufayli biroz tezroq boladi, ammo yomon holatlarda tez tartiblash uchun ish vaqti O (n^2) bolib, katta malumot toplamlari uchun qabul qilinishi mumkin emas va agar amalga oshirish togrisida yetarli malumotga ega bolsa, qasddan ishga tushirilishi mumkin, bu esa xavfsizlikka xavf tugdiradi.

Shunday qilib, O (n Enter n) tufayli, piramidal turlarga ajratish vaqtining yuqori chegarasi va yordamchi xotiraning doimiy yuqori chegarasi, real vaqtda cheklangan tizimlar yoki xavfsizlik bilan bogliq tizimlar kopincha piramidal saralashdan foydalanadilar, masalan, Linux yadrosi.

Piramidal saralash, shuningdek, bir xil vaqt oraligiga ega bolgan birlashtirilgan saralash bilan raqobatlashadi. Tartiblash, birlashtirish uchun Ω (n) yordamchi bosh joy kerak, ammo piramidal tartiblash faqat doimiy miqdorni talab qiladi. Piramida tartiblash odatda kichik yoki sekin malumot keshlari bolgan mashinalarda amalda tezroq ishlaydi va tashqi xotirani talab qilmaydi. Boshqa tomondan, birlashtirish saralash piramidal tartiblashdan bir qator afzalliklarga ega:

Birlashtiruvchi qatorlarni saralash malumotlarning keshlash samaradorligini ancha yuqori, kopincha zamonaviy ish stoli kompyuterlarida piramidal tartiblashdan ustundir, chunki saralash birlashishi kopincha qoshni xotira xujayralariga kiradi (yaxshi aloqa joylashuvi); piramidal turdagi ulanishlar uyum boylab tarqalib ketgan.

Piramidal turlarga ajratish barqaror emas. Birlashtirish tartibini yaxshi parallelizatsiya qiladi va arzimas bajarilishi bilan chiziqli tezlashishga yaqinlashishi mumkin; piramidal saralash parallel algoritm uchun aniq nomzod emas. Birlashma saralashini O(1) qoshimcha joy bilan alohida boglangan royxatlarni ishlashga moslashtirish mumkin. Piramida saralashini faqat O(1) qoshimcha kosmosga ega bolgan juft boglangan royxatlar ustida ishlash uchun moslashtirish mumkin.