14-mavzu. To’g’ridan-to’g’ri qo’shish orqali saralash. To’g’ridan-to’g’ri
almashtirish orqali saralash (pufaksimon saralash). Saralashning yaxshilagan
usullari.
Reja:
1. Ma’lumot elementlarini saralash. To’g’ridan-to’g’ri qo’shish orqali
saralash.
2. Tanlash orqali saralash usuli.
3. To’g’ridan-to’g’ri almashtirish orqali saralash (pufaksimon saralash).
Saralashning yaxshilagan usullari.
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 samaradorligini bir necha mezonlar bo’yicha baholash mumkin:
saralashga ketgan vaqt;
saralash uchun talab qilingan operativ xotira;
dasturni ishlab chiqishga ketgan vaqt.
Birinchi mezonni qarab chiqaylik. Saralash bajarilganda
taqqoslashlar yoki
almashtirishlar sonini hisoblash mumkin.
Faraz qilaylik,
N = 0,01n
