Saralash algoritmlari
![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.
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 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.
7](/data/documents/d15fd81a-9d3a-4126-9803-79f904e57552/page_7.png)
![Bu ketma-ketlik massiv saralangan holatga kelmagunicha davom etadi va
massiv saralanib bo’lishi bilan algoritm yakunlanadi.
2.2.Tanlab saralash algoritmining c++ dasturlash tilidagi dasturi
#include <iostream>
using namespace std;
int main()
{
int n, y=1, mn, nishon, s ;
cout << "Massiv elementlari sonini kiriting: ";
cin >> n ;
int a[n];
for(int i=1; i<=n ; i++)
{
cout << "A[" << i << "]= ";
cin >> a[i];
}
// massiv elementlarini kiritish uchun
for(int i=2; i<=n ; i++)
{
if(a[i-1]<a[i])
{
12](/data/documents/d15fd81a-9d3a-4126-9803-79f904e57552/page_12.png)
![y++;
}
// agar massiv elementlari saralangan tartibda berilgan
// bo'lsa y nga teng bo'lib qoladi
}
if(y==n)
{
goto nishon;
// goto shartsiz o'tish orqali nishonga qarab o'tib ketadi
// nishonning boshlanishi
}
else
{
for(int i=1; i<n ; i++)
{
mn=a[i];
for(int j=i; j<=n ; j++)
{
mn=min(mn,a[j]);
// eng kichik elementni topish uchun
if (a[j]==mn)
{
s=j;
}
// yuqoridagi if operatori massivning kichik elementini
// indeks raqamini saqlab qolish uchun
}
swap(a[i],a[s]);
13](/data/documents/d15fd81a-9d3a-4126-9803-79f904e57552/page_13.png)
![// swap funksiyasi massiv elementlarini o'rnini almashtiradi
}
}
nishon:
// shartsiz o'tish operatorining yakuni
cout << "Massivning tartiblangan xolati quyidagicha:"<< endl;
for(int i=1; i<=n ; i++)
{
cout << a[i] << " ";
}
//massivni oynaga chop etish uchun
return 0;
}
Dastur natijasi:
Dastur ishga tushirilganda
foydalanuvchidan kiritiluv-
chi ma’lumotlar sonini so‘-
raydi. Ma’lumotlar kiritil-
gandan so‘ng, dastur kiri-
tilgan ma’lumotlarni sara-
lab ekrangan chiqaradi.
Yuqoridagi dasturda foydalanuvchi massiv elementlarini saralagan holatda
kiritsa dastur uni saralashi kerak bo’lmaydi.
for(int i=2; i<=n ; i++)
{
if(a[i-1]<a[i])
{
y++;
}
14](/data/documents/d15fd81a-9d3a-4126-9803-79f904e57552/page_14.png)
![Dasturning ushbu qismi aynan shu vazifani bajarishga mo’ljallangan. Agar
massiv saralangan holatda berilsa y==n bo’ladi.
if(y==n)
{
goto nishon;
}
Y==n sharti bajarilsa shartsiz o‘tish operatori orqali daturning belgilangan
nuqtasi (metka)dan davom etib ketaveradi.
for(int i=1; i<n ; i++)
{
mn=a[i];
for(int j=i; j<=n ; j++)
{
mn=min(mn,a[j]);
if (a[j]==mn)
{
s=j;
}
}
swap(a[i],a[s]);
}
}
Har bir iteratsiyada mn nomli o’zgaruvchi o’ziga a[i] elementni qabul qilib
oladi. Yana bir takrorlash operatori mn o‘zgaruvchini qolgan elementlar bilan
taqqoslashda ishlatiladi.
mn=min(mn,a[j]);
Agar mn dan kichik element aniqlansa mn usha elemenni o‘ziga qiymat sifatida
qabul qiladi.
if (a[j]==mn)
{
15](/data/documents/d15fd81a-9d3a-4126-9803-79f904e57552/page_15.png)
![s=j;
}
Bu esa mn o‘zgaruvchidan kichik bo’lgan elementni indeksini saqlab qolish
uchun o‘zgaruvchidir.
}
swap(a[i],a[s]);
}
Dasturning bu qismi taqqoslanayotgan element va mn ni o‘rnini almashtiradi.
for(int i=1; i<=n ; i++)
{
cout << a[i] << " ";
}
Saralangan massivni ekranga chop etadi.
16](/data/documents/d15fd81a-9d3a-4126-9803-79f904e57552/page_16.png)
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