Saralash algoritmlari
Mundarija I-bob. Saralash algoritmlari ............................................................................... 4 1.1.Saralashning ichki va tashqi saralash turi mavjud: ................................... 4 1.2 Ichki saralash muammosining bayoni va samaradorlikni baholash yondashuvlari ....................................................................................................... 6 II-bob. Tanlab saralash algoritmi ...................................................................... 9 2.1.Tanlab saralash algoritmi ............................................................................. 9 2.2.Tanlab saralash algoritmining c++ dasturlash tilidagi dasturi ............... 12 2.3.Tanlab saralashning murakkabligi ............................................................ 17 Xulosa ................................................................................................................. 19 Manbalar ............................................................................................................ 20 1
Kirish Hozirgi kunlarda biz kundalik hayotimizda ko‘plab saralash algoritmlariga duch kelamiz. Aksariyat hollarda buni sezmaymiz. Saralash o‘zi nima? Bizga u nima-ga kerak? Undan qayerda foydalanamiz? Kabi savollar sizda ham bo’lsa kerak. Kundalik hayotimizda koplab saralash algoritmlarini kuzatishimiz mumkin. Oddiy dehqon yetishtirgan mahsulotlarini saralab olishi bunga misol bo‘la oladi. Bu bizga oddiy ko’rinsada uni ham ma’lum bir algoritmi mavjud bo‘ladi. Birinchi galda mahsulotlarni kattasini va sifatlisini ajratib oladi. Keyingi qadamda kichikroq sifatlilarini ajratib oladi. Keyingi qadamda esa kichik va shikastlangan mahsulotlarni ajratib oladi. Va yakunida istemolga yaroqsiz mahsulotlar ajralib qoladi. Ushbu mahsulotlarni bir joyga yig‘ganida esa mahsulotlar saralangan holatda turadi. Xuddi shu harakatlarni texnikalar ham bajara olishadi. Buning uchun texnikaga saralash algoritmi qadamlarini to‘g‘ri kiritish kifoya. Buni amalga oshirish uchun saralash nima ekanligini bilish lozim. Saralash bu berilgan ma’lumotlarni qandaydir mantiq asosida o‘z joyiga joylashtirishdir. Agar bizga A= {5, 7, 3, 1, 8, 6, 4, 2} to‘plam elementlarini o‘sish tartibida saralash topshirilgan bo’lsa, miyamiz qandaydir mantiq asosida juda tez saralab beradi.berilgan A to‘plam elementlarini taqqoslab o’rnini almashtirib joylashtirib chiqadi va bizga A={1, 2, 3, 4, 5, 6, 7, 8} to’plamni beradi. Buni mashina ham saralab berishi mumkin. Buning uchun biz mashinaga ma’lum bir saralash algoritmini dasturlash tillari yordamida, kodlar orqali tushuntiramiz. Miyyamiz bu vazifani bajarishga qiynalmaydi lekin ma’lumotlar ko‘proq bo’lsachi? Masalan 200 ta 300 ta ma’lumotni miyamiz saralab berishi mumkin lekin bunga ancha ko’p vaqt va kuch talab qilinadi. Agar ma’lumotlar bundanda ko’p bo’lsachi ? millionlab, milliartlab ma’lumotlarni saralash jarayoni ancha qiyin kechadi. Lekin mashinada bu soniyalarda bajariladi. Dunyoda raqamlangan ma’lumotlar hajmi #ekponent bo‘yicha o‘sib bormoqda. IBS kompaniyasining ma’lumotlariga qaraganda, 2003-yilda 5 eksabayt (1 eksabayt - 1 milliard gigabayt) ma'lumot yig’ilgan ekan. 2008-yilda u 0.18 zettabayt (1 zettabayt = 1024 eksabayt) gacha, 2011-yilga kelib 1.76 zettabayt, 2013-yilda 4.4 zettabaytgacha yetibdi. 2015-yilning mayida dunyoda yig‘ilgan raqamlanga ma’lumotlar hajmi 6.5 zettabaytdan oshib ketibdi. 2020- yilga kelib insoniyat 40-44 zettabayt raqamli ma’lumot hosil qilar ekan. IBS mutaxassislarining fikriga ko‘ra, 2013-yilda yig‘ilgan ma’lumotlar massivining atiga 1.5%i qandaydiy axborot qiymatiga ega bo'lgan ekan. Baxtga qarshi, hozir dunyoda katta ma’lumotlarni qayta ishlash texnologiyalari bo‘lib, 2
ular yordamida juda katta ma’lumotlar massividan insonlarga kerak, qiziq bo‘lgan, foydali ma’lumotlarni ajratib olish mumkin bo'ladi. Big data (katta ma'lumotlar) - juda katta hajmdagi bir jinsli bo'lmagan va tez tushadigan raqamli ma’lumotlar bo‘lib, ularni odatiy usullar bilan qayta ishlab bo‘lmaydi. Ba‘zi hollarda, katta ma’lumotlar tushunchasi bilan birga shu ma’lumotlarni qayta ishlash ham tushuniladi. Asosan, analiz obyekti katta ma’lumotlar deb ataladi Bunday katta ma’lumotlarni saralashda bizga saralash algoritmlari kerak bo‘ladi. Barcha saralash algoritmlar ham yetarli darajada samara beravermaydi. Qaysi biri xotiradan va yana qaysi biri vaqtdan yutqazadi. Kerakli algoritmni qo’llash dastur samaradorligini oshiradi. 3
I-bob. Saralash algoritmlari Saralash algoritmi - bu ro'yxatdagi elementlarni saralash algoritmi. Agar ro'yxat elementida bir nechta maydon bo'lsa, saralash amalga oshiriladigan maydon saralash kaliti deb ataladi. Amalda raqam ko'pincha kalit sifatida ishlatiladi va ba'zi ma'lumotlar algoritm ishlashiga hech qanday ta'sir ko'rsatmaydigan qolgan maydonlarda saqlanadi. 1.1.Saralashning ichki va tashqi saralash turi mavjud: 1.ichki saralash - bu tezkor xotiradagi ma‘lumotlarni saralash; 2. tashqi saralash - tashqi xotira (fayllar)dagi ma‘lumotlarni saralash. Saralash deganda ma‘lumotlarni xotirada muayyan tartibda uning kalitlari bo‘yicha joylashtirish, muayyan tartib deganda esa kalit qiymati bo‘yicha o‘sish (yoki kamayish) tartibida ro‘yxatning boshidan oxirigacha joylashtirish tushuniladi. Saralash algoritmlarining samaradorligini bir necha parametrlari bo‘yicha farqlash mumkin. Bu parametrlarning asosiylari quyidagilar hisoblanadi: ○ saralash uchun sarflanadigan vaqt; ○ saralash uchun talab qilinadigan tezkor xotira hajmi. Saralash algoritmlarini baholashda faqat «joyida» saralash usullarini qarab chiqamiz, ya‘ni saralash jarayoni uchun qo‘shimcha xotira zahirasi talab qilinmaydi. Saralash uchun sarf qilinadigan vaqtni esa, saralash bajarilishi jarayonida amalga oshiriladigan taqqoslashlar va o‘rin almashtirishlar soni orqali hisoblash mumkin. Ixtiyoriy saralash usulida taqqoslashlar soni O(nlog2n) dan O(n2) gacha bo‘lgan oraliqda yotadi. Ma‘lumotlarni saralashning qat'iy (to‘g'ri) va yaxshilangan usullari mavjud bo‘lib, qat‘iy usullariga quyidagilarni misol qilib olish mumkin: ○ to‘g‘ridan-to‘g‘ri qo‘yish orqali saralash usuli; ○ to‘g‘ridan-to‘g‘ri tanlash orqali saralash usuli; ○ to‘g‘ridan-to‘g‘ri almashtirish orqali saralash usuli. Bu uchala saralash usullarining samaradorligi deyarli bir xil. Lug'atlarda "saralash" (sorting) so'zi "toifalarga ajratish, tartiblash, baholash" deb ta'riflanadi, ammo dasturchilar odatda bu so'zni tor ma'noda ishlatishadi, ularga ba'zi bir aniq tartibda elementlarni qayta joylashtirishga murojaat 4
qilishadi. Bu jarayonni, ehtimol, saralash deb emas, balki tartiblash (ordering) yoki ketma-ketlik (sequencing) deb atash kerak. Biroq, saralash so'zi dasturlash jargonida allaqachon mustahkam o'rnashgan, shu sababli kelajakda "saralash" so'zini tor ma’noda "tartiblash" dan foydalanamiz. Bu shuni anglatadiki, endi "saralash" ta'rifini shakllantirishimiz mumkin, bu kelgusida ishlatiladi. Tartiblash - bu berilgan obyektlar to'plamini muayyan tartibda qayta tartibga solish jarayoni. Saralashning maqsadi elementlarni topishni osonlashtirishdir. Ehtimol, boshqa hech qanday muammo saralash muammosi kabi juda ko'p turli xil yechimlarni keltirib chiqarmagan. Butun dunyoda tan olingan eng yaxshi algoritm bormi? Umuman aytganda, yo'q. Biroq, kirish ma'lumotlarining taxminiy xususiyatlarini hisobga olgan holda, siz eng yaxshi ishlaydigan usulni tanlashingiz mumkin. Saralash usullari juda ko'p, ularning har biri o'zining afzalliklari va kamchiliklariga ega. Tartiblash algoritmlari katta amaliy ahamiyatga ega, ular o'zlari uchun qiziqarli. Bu juda chuqur o'rganilgan informatika sohasi axborot qidirish tizimlarida, harbiy sohada va bank sohalarida ko’proq qo'llaniladi. Ammo hozirgi kunda axborot oqimini tartiblash masalasi deyarli har bir sohaga kirib bordi. Algoritmlarni saralashga bo'lgan umumiy ilmiy qiziqishdan tashqari, har bir algoritmda uning murakkabligi deb ataladigan narsani baholash qiziq. Murakkablik algoritmning boshlang'ich bosqichlarining maksimal soni sifatida tushuniladi. Tartiblash misollari algoritmni murakkablashtirish orqali qanday ko'rsatilishi mumkin, garchi hozirda aniq usullar mavjud bo'lsa-da, siz samaradorlikda sezilarli yutuqqa erishishingiz mumkin. Massivlarni saralash masalasini yechishda odatda qo'shimcha xotiradan foydalanishni minimallashtirish talabi qo'yiladi, bu esa qo'shimcha massivlardan foydalanishga yo'l qo'yilmasligini anglatadi. Algoritmlarning ishlashini baholash uchun turli xil tartiblash usullarida, qoida tariqasida quyidagi ikkita ko'rsatkich qo'llaniladi: • o’zlashtirishlar (ta’minlashlar, =) soni; • taqqoslashlar (>, <) soni; Quyidagi ko'rsatkichlar ham muhimdir: Xotira. Bir qator algoritmlar ma'lumotlarni vaqtincha saqlash uchun qo'shimcha xotira ajratishni talab qiladi. Amaldagi xotirani baholashda boshlang’ich massiv egallagan joy, kirish ketma-ketligidan mustaqil sarflangan xotira, masalan, dastur kodini saqlash uchun ajratilgan joy hisobga olinmaydi. 5