Mavzu: Algoritmlar va ma’lumotlarning dastur bilan bog’liqligi Reja

5. Razriyadlar bo’yicha saralash va izlash
Navbat nazariyasi
kutish chiziqlarini matematik o'rganish yoki navbat.^[1] Navbatning davomiyligi va kutish vaqtini taxmin qilish uchun navbat modeli ishlab chiqilgan.^[1] Navbat nazariyasi odatda operatsiyalarni o'rganish natijalar ko'pincha xizmat ko'rsatish uchun zarur bo'lgan resurslar to'g'risida biznes qarorlar qabul qilishda ishlatiladi.
Navbat nazariyasi o'zining tadqiqotlarini kelib chiqadi Agner Krarup Erlang u Daniyaning Kopengagen telefon almashinuvi kompaniyasi tizimini tavsiflovchi modellarni yaratganida.^[1] O'shandan beri g'oyalar, jumladan dasturlarni ko'rdi telekommunikatsiya, transport muhandisligi, hisoblash^[2]va, xususan sanoat muhandisligi, fabrikalar, do'konlar, idoralar va shifoxonalarni loyihalashda, shuningdek loyihalarni boshqarishda
Mazkur mavzuda algoritmlarning yangi sinfi - saralash
algoritmlarini oʻrganamiz. Ma‘lumotlarni qayta ishlashda ma‘lumotning
axborot (info) maydonini bilish va uni mashinada joylashishini tasavvur
qilish juda muhimdir.
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:
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.
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 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.