50
3-§. Saralash algoritmlari. Eng oddiy algoritmlar. Past baho
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(nlog
2
n) dan O(n
2
) gacha boʻlgan oraliqda
yotadi.
Ma‘lumotlarni saralashning
