Kompyuter savodxonligi

9.5. Axborotlarni saralash va tartiblash.
Ma’lumotlar omborida yozuvlarni tartiblash.
Barcha zarur axborotlar kompyuterga kiritilgach, ma’lumotlar omborida
ularni ma’lum tartibda tartiblab chiqish kerak bo‘ladi. Bu amal kompyuterda
qanday bajarilishi bilan tanishib chiqamiz. Masalan, "kutubxona" ma’lumotlar
omborida axborotlar o‘quvchining kodi bo‘yicha, bir o‘quvchiga tegishli axborotlar
esa kitoblar kodi bo‘yicha tartiblab chiqilishi kerak bo‘lsin. Buning uchun
kompyuter ma’lumotlar omboridagi birinchi va ikkinchi yozuvlarni bir-biri bilan
solishtiradi va ikkinchi yozuv birinchisidan avval kelishi kerak bo‘lsa, ularning
o‘rnini almashtiradi. So‘ngra birinchi yozuv bilan uchinchi yozuvni bir-biri bilan
solishtiradi va, lozim topsa, ularning o‘rnini almashtiradi. Bu jarayonni davom
ettirib, birinchi yozuvni (yoki uning o‘rniga kelgan yozuvni) navbati bilan to‘rtinchi,
beshinchi va hokazo oxirgi yozuv bilan solishtiradi. Natijada birinchi yozuv o‘rnida
birinchi o‘rinda turishi kerak bo‘lgan yozuv paydo bo‘ladi.
Shu jarayon ikkinchi qadamda ikkinchi yozuvdan boshlab takrorlanadi va
ikkinchi yozuv o‘rnida qolgan yozuvlar orasidagi eng avval turishi kerak bo‘lgan yozuv
paydo bo‘ladi. Bu jarayon uchinchi, to‘rtinchi va hokazo yozuvlar uchun takrorlanib,
butun ombor tartiblanib chiqiladi. Bu usulda tartiblash ancha vaqt talab qiladi va
hozirgi paytda bundan ko‘ra tezroq ishlaydigan tartiblashlar ham ishlatiladi.
Tartiblash amali bir marta bajarilgach, tartiblangan ombordan foydalanish
ancha qulay bo‘lib, tez bajariladi. Masalan, biror yozuvni topish uchun tartiblangan
omborda quyidagi ishlar bajariladi. Omborda 2000 ta yozuv bo‘lsin. Dastur avval
ularning o‘rtadagisi – 1000-yozuvni qidirilayotgan yozuv bilan solishtiradi. Bunda
uch hol bo‘lishi mumkin: 1000-yozuv qidirilayotgan yozuv bilan bir xil, u holda
qidirish to‘xtatiladi. Agar qidirilayotgan yozuv 1000-yozuvdan avval joylashganligi
ma’lum bo‘lsa, u holda 1-yozuvdan 1000-yozuvgacha bo‘lgan oraliq ikkiga bo‘linadi va
uning o‘rtasidagi 500-yozuv qidirilayotgan yozuv bilan solishtiriladi. Aks holda,
ya’ni qidirilayotgan yozuv 1000-yozuvdan keyin joylashgan bo‘lsa, 1000- va 2000-
yozuvlar o‘rtasiga joylashgan 1500-yozuv qidirilayotgan yozuv bilan solishtiriladi.
107
Ikkala holda ham qidirish oralig‘i ikki marta qisqardi va 2000 ta yozuvdan
1000 ta yozuvga kamaydi. Bu amalni takrorlab, keyingi qadamda qidiruv 500 ta yozuv
orasida bajariladi. Bu jarayon bir necha qadamdan keyin to‘xtaydi: qidirilayotgan
va solishtirilayotgan yozuvlar bir-biriga teng bo‘ladi yoki qidirish oralig‘i
uzunligi birga teng bo‘lib qoladi.
Agar qidirilayotgan yozuvdan bir nechtasi mavjud bo‘lsa, u holda avval ulardan
birinchisi topiladi, so‘ngra ularning nechtaligi aniqlanadi. Yuqoridagi qidirish
amali 2000 ta yozuv uchun bajarilganda yozuvlarni o‘zaro solishtirishlar soni
2000*2001/2≈1000000 ga teng bo‘lsa, bitta yozuvni qidirib topish amalida
solishtirishlar ko‘pi bilan log22000=11 ta bo‘lishi mumkin.