|
Kurs ishining maqsadi: Algoritmlashda Piramidal saralalash usulini o’rganish va uni tahlil qilish.
Kurs ishining vazifasi: Algoritmlashda Piramidal saralash usuli yordamida masalalarni hal qilish.
Kurs ishining dolzarbligi: Ushbu kurs ishini o’rganishda o’quvchilar piramidal saralash haqida bilim va ko’nikmalarga ega bo’lishadi. Dasturlashda piramidal saralash usulini qo’llashni va undan unumli foydalanishni o’rganadilar.
I BOB. NAZARIY QISM
1.1 Saralash haqida tushuncha.
Nima uchun kerak? Saralash va izlash amalda juda ko’p qo’llaniladi, fayldagi so’zlarnini izlashdan tortib, internetda ma’lumot izlashgacha.
a[0], a[1], a[2] .. a[n-1] massiv elementlari berilgan.
Ularni shunday joylashtirish kerakki, ular kamaymaslik tartibida bo’lib qolsin.
Masalan:
5 8 9 1 5 2 3 9
Saralangandan so’ng
1 2 3 5 5 8 9 9
Saralash deb, berilgan ob’yektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktab jismoniy tarbiya darsi. Bu dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida esa sinf jurnalidagi familyalar ketma-ketligiga qarab topshirishadi. Shu yerning o`zida 2ta saralashdan foydalanilyapti. Biri, bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalidagi o`rinlar bo`yicha.
Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma-bir tahlil qilib chiqamiz (buning uchun saralanmagan sonlar ketma-ketligini olamiz):
Sonlar berilishi: 23, 54, 3, 22, 1, 45;
Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o`z o`rnida turibdi)
Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son)
Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi)
Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi)
Demak, miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma`lumki, bizning miyamiz o`zi optimal deb bilgan yo`nalishdan ketadi va biz uchun faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo`lmaydi. Dasturlashga talab ortib, bu soha rivojlanib borgani sari unda bir qator sohalardagi kabi tezlikni oshirish muammosi paydo bo`ladi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o`rinda savol tug`iladi, operatsion tizimlarda ham saralashdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil saralash mavjud: fayl turi, nomi, o`zgartirilgan sanasi va o`lchami. Har birini o`sish yoki kamayish tartibida saralash mumkin. Ha aytgancha, hozirgi tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki tezlik masalasi tobora yuqori cho`qqiga chiqayotgan va ishlanayotgan ma`lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish kulguli. Ma`lumotlar o`lchamlari esa juda katta, shu sabali ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga oshirish uchun esa yangi algoritmlarga ehtiyoj tug`ila boshladi. Buni yechimi sifatida bir necha turdagi algoritmlardan foydalaniladi. Ular:
Bubble sort;
Selection sort;
Insertion sort;
Quick sort;
Merge sort.
Samarali tartiblash optimallashtirish uchun muhimdir samaradorlik boshqa algoritmlarning (masalan qidirmoq va birlashtirish algoritmlar) kirish ma'lumotlarini saralangan ro'yxatlarda bo'lishini talab qiladi. Saralash ham ko'pincha foydalidir kanonizatsiya qilish ma'lumotlar va inson tomonidan o'qiladigan mahsulotni ishlab chiqarish uchun. Rasmiy ravishda har qanday saralash algoritmining chiqishi ikkita shartni qondirishi kerak:
Chiqish kamaytirilmaydigan tartibda (har bir element kerakli darajada oldingi elementdan kam emas umumiy buyurtma);
Chiqish a almashtirish (qayta tartibga solish, ammo barcha asl elementlarni saqlab qolish) kirishning.
Bundan tashqari, kirish ma'lumotlari ko'pincha an-da saqlanadi qator bu imkon beradi tasodifiy kirish, ro'yxat o'rniga, faqat ruxsat beradi ketma-ket kirish; mos algoritmlardan so'ng har qanday ma'lumot turiga ko'plab algoritmlarni qo'llash mumkin.
Tartiblash algoritmlari ko'pincha "sort" so'zidan keyin so'z deb nomlanadi va grammatik jihatdan ingliz tilida ism iboralari sifatida ishlatiladi, masalan, "katta ro'yxatlarga qo'shish tartibini ishlatish samarasiz" iborasi qo'shish tartibi ga ishora qiladi qo'shish tartibi saralash algoritmi. Hisoblashning boshidan boshlab, saralash muammosi juda ko'p tadqiqotlarni jalb qildi, ehtimol bu oddiy, tanish bayonotga qaramay, uni samarali hal qilishning murakkabligi tufayli. Dastlabki saralash algoritmlari mualliflari orasida 1951 yil ham bo'lgan Betti Xolberton (tug'ilgan Snayder) Bubble sort 1956 yilidayoq tahlil qilingan. Taqqoslash tartiblash algoritmlari asosiy talabga ega Ω (n jurnal n) taqqoslashlar (ba'zi kirish ketma-ketliklari ko'paytmani talab qiladi n jurnal n taqqoslashlar, bu erda n - qatorga ajratiladigan elementlar soni). Kabi taqqoslashga asoslanmagan algoritmlar hisoblash turi, yaxshi ishlashga ega bo'lishi mumkin. Asimptotik optimal algoritmlar 20-asr o'rtalaridan beri ma'lum bo'lgan - foydali yangi algoritmlar hali ham ixtiro qilinmoqda, hozirda keng qo'llanilmoqda Timsort 2002 yilga tegishli va kutubxona birinchi marta 2006 yilda nashr etilgan.
Kirish qismida saralash algoritmlari keng tarqalgan Kompyuter fanlari masalan, algoritmlarning ko'pligi turli xil asosiy algoritm tushunchalari bilan yumshoq tanishishni ta'minlaydigan sinflar, katta O yozuvlari, algoritmlarni ajratish va yutish, ma'lumotlar tuzilmalari kabi uyumlar va ikkilik daraxtlar, tasodifiy algoritmlar, eng yaxshi, eng yomon va o'rtacha ish tahlil, vaqt-makon savdo-sotiqlarida yuqori va pastki chegaralar.
Kichik massivlarni maqbul (hech bo'lmaganda taqqoslash va almashtirish) yoki tez (masalan, mashinaning o'ziga xos tafsilotlarini hisobga olgan holda) saralash hali ham juda kichik massivlar uchun ma'lum bo'lgan echimlarga ega bo'lgan ochiq tadqiqot muammosi (<20 element). Xuddi shunday maqbul (har xil ta'rifga ko'ra) parallel mashinada saralash ham ochiq tadqiqot mavzusi.
Algoritmlarning grafik shaklida tasvirlanishida algoritmlar maxsus geometrik figuralar yordamida tasvirlanadi va bu grafik ko‘rinishi blok-sxema deyiladi. Blok-sxemalar bilan ishlashni yaxshilab o‘zlashtirib olish zarur, chunki bu usul algoritmlarni ifodalashning qulay vositalaridan biri bo‘lib programma tuzishni osonlashtiradi, programmalash qobiliyatini mustahkamlaydi. Algoritmik tillarda blok - sxemaning asosiy strukturalariga maxsus operatorlar mos keladi. Shuni aytish kerakni, blok-sxemalardagi yozuvlar odatdagi yozuvlardan katta farq qilmaydi.
Do'stlaringiz bilan baham: |
