6
Agar saralanayotgan yozuvlar xotirada katta xajmni egallasa, u holda ularni almashtirishlar
katta sarf (vaqt va xotira ma’nosida) talab qiladi. Ushbu sarfni kamaytishi maqsadida, saralash
kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma’lumot ko’rsatkichlari
almashtirilib, massiv o’z joyida qoladi. Yuqoridagi usul adreslar jadvalini saralash usuli deyiladi.
Saralanayotganda bir hil kalitlar uchrashi mumkin, bu holda saralanagandan
keyin bir hil
kalitlilar boshlang’ich tartibda qanday joylashgan bo’lsa, ushbu tartibda qoldirilishi maqsadga
muvofiq bo’ladi (Bir hil 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
soni hisoblash mumkin.
Faraz qilaylik, N = 0,01n
2
+ 10n – taqqoslashlar soni. Agar n < 1000 bo’lsa, u holda ikkinchi
qo’shiluvchi katta, aks holda ya’ni, n > 1000 bo’lsa, birinchi qo’shiluvchi katta bo’ladi.
Demak, kichkina n larda taqqoslashlar soni n ga teng bo’ladi,
katta n larda esa n
2
ga teng
bo’ladi.
Saralashda taqqoslashlar soni quyidagi oraliqlarda bo’ladi:
0(n log n) dan 0 (n
2
) gacha; 0 (n) – ideal holatda.
Saralashni quyidagicha usullari bor:
qat’iy (to’g’ridan-to’g’ri) usullar.
yaxshilangan usullar.
