Kurs ishi bajardi: S2-kt-21 guruh talabasi
O`ZBEKISTON RESPUBLIKASI OLIY TA`LIM, FAN VA INNOVATSIYALAR VAZIRLIGI
OSIYO XALQARO UNIVERSITETI
“Umumkasbiy fanlar” kafedrasi
“Algoritmlar va ma'lumotlar strukturalari”
FANIDAN
KURS ISHI
Bajardi: S2-KT-21 guruh talabasi
Haydarova S.S
Qabul qildi: Abidov K.Z.
BUXORO – 2023
Mavzu: To`g`ridan to`g`ri saralash algoritmlari va dasturlari.
Reja:
Tuzilma elementlarini saralash.
To'g'ridan-to'g'ri qo'shish usuli bilan saralash algoritmi.
Piramidali saralash usuli.
Tuzilma elementlarini saralash
Ma'lumotlarni kompyuterda qayta ishlashda elementning informatsion maydoni va uning mashina xotirasida joylashishini bilish zarur. Shu maqsadda ma'lumotlarni saralash amalga oshiriladi. Demak, saralash – bu ma'lumotlarni kalitlari bo'yicha doimiy ko'rinishda mashina xotirasida joylashtirishdan iborat. Bu yerda doimiylik ma'lumotlarni massivda kalitlari bo'yicha o'sishi tartibida berilishi tushuniladi.
Ma'lumotlarga qayta ishlov berilayotganda ma'lumotning informatsion maydonini hamda uning mashinada joylashishini (adresini) bilish zarur.
Saralashning ikkita turi mavjud: ichki va tashqi:
ichki saralash bu operativ xotiradagi saralash;
tashqi saralash – tashqi xotirada saralash.
Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma'nosida) talab qiladi. Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma'lumot ko'rsatkichlari almashtirilib, massiv o'z joyida qoladi. Bu usul adreslar jadvalini saralash usuli deyiladi.
Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir xil kalitlilar boshlang'ich tartibda qanday joylashgan bo'lsa, shu tartibda qoldirilishi maqsadga muvofiq bo'ladi (Bir xil kalitlilar o'zlariga nisbatan). Bunday usulga turg'un saralash deyiladi.
Saralash – bu bеrilgan to`plam elеmеntlarini birоr bir tartibda jоylashtirish jarayonidir. Saralashni maqsadi tartiblangan to`plamda kеrakli elеmеntni tоpishni оsоnlashtirishdan ibоrat. Saralash dasturlarni translyaciya qilinayotganda, ma’lumоtlar majmuasini tashqi хоtirada tashkil qilinayotganda, kutubхоnalar, katalоglar, ma’lumоtlar bazasi yaratilayotganda tadbiq qilinadi. Ma’lumki, saralashning turli hil algоritmlari mavjud. Sababi, bitta masalani saralash uchun juda ko`plab turli hil algоritmlardan fоydalanish mumkin. Bеrilgan masalani hal qilishda ba’zilari mukammal bo`lishi mumkin. Shuning uchun saralash masalasida algоritmlarni qiyosiy tahlilini o`tkazish zarurati paydо bo`ladi. Saralash masalasini qo`yilishini quyidagicha yozish mumkin.
F araz qilaylik, a1, a2 ,…, an, elеmеntlar kеtma-kеtligi bеrilgan bo`lsin. U hоlda saralash algоritmi elеmеntlarni massivga shunday jоylashtiradiki, natijada ular qandaydir munоsabatga nisbatan
f(ak1) f(ak2) … f(akn) tartibga ega bo`ladi.
Оdatda f tartiblash funkciyasi qandaydir maхsus qоida bilan hisоblanmasdan, balki elеmеntni kalit qiymati bo`yicha massiv elеmеntlari tartiblanadi.
Ma’lumоtlarga qayta ishlоv bеrilayotganda ma’lumоtni infоrmaciоn maydоnini hamda uni mashinada jоylashishini (adrеsini) bilish zarur.
Saralashni ikkita turi mavjud: ichki va tashqi:
ichki saralash bu оpеrativ хоtiradagi saralash;
tashqi saralash – tashqi хоtirada saralash.
Saralash bu ma’lumоtlarni kalitlari bo`yicha хоtirada rеgulyar ko`rinishda jоylashtirishdir. Rеgulyarlik dеganda ma’lumоtlar kalit qiymatlari bo`yicha massivda bоshidan охirigacha o`sishi yoki kamayishi tushiniladi.
Agar saralanayotgan yozuvlar хоtirada katta хajmni egallasa, u hоlda ularni almashtirishlar katta sarf (vaqt va хоtira ma’nоsida) talab qiladi. Ushbu sarfni kamaytishi maqsadida, saralash kalitlar adrеsi jadvalida amalga оshiriladi. Bunda faqatgina ma’lumоt ko`rsatkichlari almashtirilib, massiv o`z jоyida qоladi. YUqоridagi usul adrеslar jadvalini saralash usuli dеyiladi.
Saralanayotganda bir hil kalitlar uchrashi mumkin, bu hоlda saralanagandan kеyin bir hil kalitlilar bоshlang’ich tartibda qanday jоylashgan bo`lsa, ushbu tartibda qоldirilishi maqsadga muvоfiq bo`ladi (Bir hil kalitlilar o`zlariga nisbatan). Bunday usulga turg’un saralash dеyiladi.
Saralash samaradоrligini bir nеcha mеzоnlar bo`yicha bahоlash mumkin:
saralashga kеtgan vaqt;
saralash uchun talab qilingan оpеrativ хоtira; dasturni ishlab chiqishga kеtgan vaqt.
Birinchi mеzоnni qarab chiqaylik. Saralash bajarilganda taqqоslashlar yoki almashtirishlar sоni hisоblash mumkin.
Faraz qilaylik, N = 0,01n2 + 10n – taqqоslashlar sоni. Agar n < 1000 bo`lsa, u hоlda ikkinchi qo`shiluvchi katta, aks hоlda ya’ni, n > 1000 bo`lsa, birinchi qo`shiluvchi katta bo`ladi.
Dеmak, kichkina n larda taqqоslashlar sоni n ga tеng bo`ladi, katta n larda esa n2 ga tеng bo`ladi.
Saralashda taqqоslashlar sоni quyidagi оraliqlarda bo`ladi:
0(n log n) dan 0 (n2) gacha; 0 (n) – idеal hоlatda. Saralashni quyidagicha usullari bоr:
qat’iy (to`g’ridan-to`g’ri) usullar;
yaхshilangan usullar.
Qat’iy usullar:
to`g’ridan-to`g’ri qo`shish usuli;
to`g’ridan-to`g’ri tanlash usuli;
to`g’ridan-to`g’ri almashtirish usuli.
YUqоrida kеltirilgan uchala usulda ham almashtirishlar sоni dеyarli bir hil bo`ladi.
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
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 samaradorligi
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
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:
1) to‘g‘ridan-to‘g‘ri qo‘yish orqali saralash usuli;
2) to‘g‘ridan-to‘g‘ri tanlash orqali saralash usuli;
3) to‘g‘ridan-to‘g‘ri almashtirish orqali saralash usuli;
Bu uchala saralash usullarining samaradorligi deyarli bir xil.
Tartiblash
Tartiblash - bu berilgan obyektlar to'plamini muayyan tartibda qayta tartibga solish jarayoni. Saralashning maqsadi elementlarni topishni osonlashtirishdir.
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.
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.
Murakkablik
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;
Ko'pgina hollarda, ma'lumotlarning ba'zi bir mezonlarga muvofiq tartiblanishi ma'lumotlarni qayta ishlashni soddalashtiradi. Masalan, ikkilik qidiruvni ketma-ket qidirishni amalga oshirishda vaqtni sezilarli darajada tejash, ikkilik yoki boshqa turdagi qidiruv algoritmlarini amalga oshirishda katta yutuqlarni ta'minlash uchun ma'lumotlar to'plamini oldindan saralashga vaqt sarflash uchun yetarli sababdir.
Eng muhimi, in situ (joylashtirish) bo’yicha tartiblash algoritmlari bo'lib, ular tartiblangan ketma-ketlikni egallagan xotira maydoni ichidagi elementlarning almashinishini ta'minlaydi. Bunday holda, ma'lumotlar ketma-ketligi odatda tezkor xotirada joylashgan massiv sifatida tushuniladi - bunday massivlarni saralash ichki saralash deb ataladi, aksincha tashqi saralash - ba'zi tashqi manbalardan ma'lumotlarni olish (masalan, diskdagi fayl) sifatida tushuniladi.
Algoritmni tahlil qilish
Odatda ma'lumotlar ba'zi bir muhim qiymatlarning ko'tarilish yoki kamayish tartibida saralanadi.
Algoritmni tahlil qilish ushbu algoritm yordamida muammoni hal qilish uchun qancha vaqt sarflanishi haqida tasavvurga ega bo'lishni o'z ichiga oladi. Algoritmni baholashda, ma'lum bir algoritm uchun uning ishlashi davomida eng muhim bo'lgan amallar sonidan kelib chiqadi. Saralash algoritmlari uchun bunday amallar asosiy taqqoslash amallari va tartiblangan elementlarning uzatish amallari hisoblanadi.
Algoritm samaradorligini baholashda, odatda, uchta variantni baholashga harakat qilinadi: eng yaxshi holat (vazifa eng qisqa vaqt ichida amalga oshirilganda), eng yomon holat (vazifa maksimal vaqt ichida amalga oshirilganda) va o'rta holat , (buni odatda tahlil qilish eng qiyin). Algoritmlarni saralashning asosiy ko'rsatkichlari bu algoritm ishlashi davomida amalga oshirilgan taqqoslash va almashtirishlarning o'rtacha soni.
Algoritm samaradorligini baholashda
Shu bilan birga, algoritm tomonidan bajariladigan amallar sonini aniq bilish samaradorlikni tahlil qilish nuqtai nazaridan juda muhim emas. N - massiv elementlari sonining ko'payishi bilan amallar sonining o'sish sur'ati muhimroqdir.
O'sish sur'atlarining asosiy sinflarining vizual jadvalida: log2n, n, n log2n,
n2, n3, 2n ko’rinishidagi baholarga ega bo’lish mumkin. Algoritmning umumiy samaradorligini baholashda tez o'sib boruvchi funksiyalar ustunlik qiladi, shuning uchun, agar algoritmning murakkabligi chiziqli va kvadratik funktsiyalarning yig'indisi bo'lsa, u holda chiziqli funktsiyani bekor qilish kerak va o'sish darajasi n2 bilan taqqoslanadigan funktsiya sifatida baholanadi.
Algoritm samaradorligi
Algoritm samaradorligini baholash nuqtai nazaridan eng muhimi O(f) deb belgilangan funktsiyalar sinfidir ("katta O" o'qing),
Bu f dan tez bo'lmagan funksiyalardan iborat. Bunday holda, f(O) f sinf uchun yuqori chegara. Algoritmlarni baholash uchun ushbu murakkablik sinfining ahamiyati quyidagi holat bilan izohlanadi. Agar bitta algoritmning murakkabligi ikkinchisining murakkabligining "katta" sinfiga mansubligini ko'rsatish mumkin bo'lsa, demak, bu ikkinchi algoritm masalani birinchisidan yaxshiroq hal qiladi.
O belgisini P. Baxman 1892-yilda "Analytische Zahlentheorie" kitobida kiritgan (qarang [Knuth, 1968]). Aslida, murakkablik sinfining kiritilishi, baholash funktsiyalarida taxminiy tenglik belgisini teng belgi bilan almashtirishga imkon beradi. F (n) funktsiyasi uchun n bo'lgan joyda aniq qiymati noma'lum bo'lgan miqdorni belgilash uchun O (f (n)) yozuvi ishlatiladi.
Saralash algoritmlari va ularning tahlili.
Pufaksimon saralash (Bubble sort)
Ushbu algoritmda biz massiv takrorlash bilan boshlaymiz va birinchi elementni ikkinchisiga taqqoslaymiz va agar ular noto'g'ri tartibda joylashgan bo'lsa, ularni almashtiramiz, keyin ikkinchi va uchinchisini taqqoslaymiz va hokazo. Ushbu takrorlashdan so'ng eng katta element quyida keltirilgan rasmda ko'rsatilgandek massivning oxiriga o'tadi.
Pufaksimon saralash (Bubble sort)
Pufaksimon saralash (Bubble sort)
Endi eng katta element o’z joyini egallaydi, shuning uchun biz yana ushbu jarayonni takrorlaymiz va allaqachon o'z pozitsiyalarida bo'lgan elementlarni qoldiramiz va bu tartiblangan massivni beradi.
Pufaksimon saralash (Bubble sort) algoritmining C++ dastur kodi
Bubble Sort eng mashhur saralash algoritmlaridan biridir. Bu yerda siz qo'shni elementlarning qiymatlarini ketma-ket taqqoslashingiz va agar oldingisi keyingisidan kattaroq bo'lsa, raqamlarni almashtirishingiz kerak. Shunday qilib, katta qiymatlarga ega elementlar ro'yxatning oxirida, pastroq qiymatlar esa boshida qoladi.
Ushbu algoritm ta'limiy hisoblanadi va samaradorligi pastligi sababli amalda deyarli hech qachon qo'llanilmaydi: u kichik elementlar (ular "toshbaqalar" deb nomlanadi) massiv oxirida joylashgan testlarda sekin ishlaydi. Biroq, ko'plab boshqa usullar bunga asoslangan, masalan, Sheyker saralash va taroqsimon saralashlari.
Sheyker saralashi. Sheyker (kokteyl) saralashi - bu Pufaksimon (Bubble Sort) algoritmining varianti. Bubble sort algoritmi har doim chapdan elementlarni aylanib o'tadi va birinchi iteratsiyada eng katta elementni to'g'ri holatiga, ikkinchisida esa ikkinchi takrorlashda va hokazo. Kokteyl saralash berilgan qator orqali har ikki yo'nalishda ham muqobil ravishda harakatlanadi.
Algoritm:
Algoritmning har bir takrorlanishi 2 bosqichga bo'linadi:
Birinchi bosqich massivni xuddi Bubble Sort singari chapdan o'ngga aylantiradi. Sikl davomida qo'shni elementlar taqqoslanadi va agar chapdagi qiymat o'ngdagi qiymatdan katta bo'lsa, qiymatlar almashtiriladi. Birinchi takrorlash oxirida eng katta son massivning oxirida bo'ladi.
Taroqsimon saralash
Taroqsimon saralash – “Pufaksimon” saralashning yaxshiroq varianti. Uning g'oyasi algoritmni sekinlashtiradigan qator oxiridagi kichik qiymatlarga ega elementlarni "yo'q qilish". Agar pufakchali va shirker saralashlarida, massiv bo'ylab takrorlanganda qo'shni elementlar taqqoslansa, u holda "tarash" paytida avval taqqoslangan qiymatlar orasida yetarlicha katta masofa olinadi, so'ngra u minimal darajaga tushadi.
Dastlabki bo'shliq tasodifiy tanlanmasligi kerak, lekin maxsus qiymatni hisobga olgan holda - kamaytirish qiymati, uning optimal qiymati 1,247 ga teng. Dastlab elementlar orasidagi masofa massivning kattaligiga 1,247 ga teng bo'ladi; har bir keyingi bosqichda masofa yana qisqartirish koeffitsiyentiga bo'linadi - va shunga o'xshash jarayon algoritm oxirigacha davom etadi.
To’liq saralanmagan massiv
Qisman tartiblangan massiv
|
