Mavzu: Axborotlarni saralash va tartiblash. Ma’lumotlar omborida yozuvlarni tartiblash

Mavzu: 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.
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 nechta 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 log₂2000=11 ta bo’lishi mumkin.