Kirish: I. Ma’lumotlar tuzilmasini saralash usullari

II. Ma’lumotlarni saralash va izlash algoritmlari.

2.1. Ma’lumotlarni tartibga solish tushunchasi.

Agar ma’lumotlar KOMPYUTER xotirasida muayyan tartibda

saqlanadigan bo’lsa axborotga ishlov berish va uni izlash bilan bog’liq ko’p

masalalar tezroq, oddiyroq va samaraliroq hal qilinadi. Bir qator hollarda

ma’lumotlarning tartibga solinganligidan foyda aniq ravshan va maxsus

isbotlashlarni talab etmaydi. Agar lug’at yoki telefon ma’lumotnomasida

so’zlar va familiyalar alifbo tartibida joylashtirilmaganda ulardan

foydalanish qanchalik qiyin bo’lishini tasavvur etish mumkin. Lekin

ma’lumotlarni saralash zaruriyati masalasi har safar muayyan vazifaga

nisbatan hal qilinishi zarur. Bunda tashqi xotira qurilmalari imkoniyatlari,

operativ xotira hajmi, ma’lumotlarga murojaat qilish tezligi, ularni yangilab

turish tezligi va ishlov berish xarakteri kabilarni tahlil qilish zarur.

Turli ilovalarda tartibga solishning turli mezonlaridan foydalaniladi.

Ma’lumotlar ularga murojaat qilish ehtimolining qiymati, qancha tez-tez

murojaat etib turilishiga ko’ra tartibga solinishi mumkin. Odatda tartibga

solish kalit bo’yicha amalga oshiriladi.

Axborot tizimlari bilan ishlov beriladigan ma’lumotlar birligi bir qator

axborot maydonlaridan iborat bo’lgan yozuv hisoblanadi. Kalit bitta yozuv

maydoni ichidagi narsalar (kalit maydoni) yoki muayyan maydonlar

majmuidan iborat bo’lishi mumkin. Keyingi holda kalit tarkibiy deb ataladi.

YOzuv faqat bittagina maydondan iborat bo’lishi mumkin va u bu holda

kalitli hisoblanadi. Tartibga solish natijasida yozuvlar kalitlarning qiymati

oshib borishi yoki kamayib borish bo’yicha joylashadi. Masalan, fakulbtet

talabalari to’g’risidagi ma’lumotlardan iborat bo’lgan yozuvlar talabalarningzachet daftarchalari nomerilari bo’yicha tartibga solingan bo’lishi mumkin.

Yozuvlarni kalitlarining qiymati oshib borishi yoki kamayib borishi

bo’yicha tartibga solish jarayoni saralash deb ataladi.

Ba’zan, ayniqsa yozuvlarning kaliti tarkibiy bo’lgan hollarda, tartibga

solingan yozuvlar ichida ham tartibga solish zarur bo’ladi, Masalan,

fakulbtetning barcha talabalari to’g’risidagi yozuvlar guruhlarning nomerlari bo’yicha, har bir guruh ichida esa familiyalarning birinchi harfi alifbo tartibida tartibga solingan bo’lishi mumkin. Bu holda guruh nomeri katta,familiyaning harfi esa kichik kalit bo’ladi.

Umuman olganda kalitlarning bir nechta darajalarini belgilash

mumkin, bunda katta kalit birinchi rang kaliti, kichik kalitlar esa tegishlicha

ikkinchi, uchinchi rang kalitlari deb ataladi va hokazo. Bu holda saralash

bosqichma-bosqich amalga oshiriladi. Dastlab yozuvlar massivi birinchi

rang kaliti bo’yicha saralanadii So’ngra birinchi rang kalitining qiymatlari

bir xil bo’lgan yozuvlar ikkinchi kalit rangi bo’yicha saralanadi va hokazo.

Masalan, lug’atning birinchi rang kaliti so’zning birinchi harfi, ikkinchi rang kaliti esa ikkinchi harfi va hokazo bo’ladi.

Saralash jarayonida yozuvlar xotirada shunday jismoniy surilishi

mumkinki, bunda kichik kalitli yozuv katta kalitli yozuvdan oldinda

joylashib qoladi. Lekin har doim ham jismoniy surilish majburiy bo’lmaydi.Bir qator hollarda yordamchi jadval tuzish va uning yordamida kalitlarining

tartibiga muvofiq joylashgan yozuvlardan erkin foydalanish ta’minlanadi.

Masalan, ko’rsatkichlar vektoridan foydalanish mumkin, uning har elementiyozuvning indeksi yoki manzilidan iborat bo’ladi. Vektor elementlariningyurish tartibi asosiy massiv elementlarining tartibga solingan ketma-ketliginibelgilab beradi.

Kalit maydonida sonli yoki belgili ma’lumotlar saqlanishi mumkin.

Kalitining xarakteriga ko’ra yozuvlar sonli usulda yoki alifbo-raqamli usuldasaralanadi. Sonli saralashda yozuvlar kalitining qiymatiga qarab oshibboradigan yoki kamayib boradigan tarzda tarbiga solinadi. Agar kalit

Maydonida belgili ma’lumotlar saqlanayotgan bo’lsa, saralashda

belgilarning qatorlari solishtiriladi. Saralash natijasida massiv yozuvlarining leksik-grafik tartibda joylashish tartibi belgilanadi. Simvollarni solishtirishda ularni kompyuterda taqdim etishning ikkilamchi kodlari solishtiriladi. Katta kodga ega bo’lgan belgi katta hisoblanadi.

Simvollarning qatoralrini solishtirish muayyan qoidalarga muvofiq

amalga oshiriladi. Aytaylik, lotin alifbosi belgilarining ikki qatori

solishtirilayapti: X1X2 ... Xm va Y1Y2 ... Yn, bu erda Xi va Yi - belgilar,

ularning har biriga muayyan ikkilangan kod to’g’ri keladi. X1X2 ... Xm

qatori quyidagi hollarda Y1Y2 ... Yn qatoridan kichik deb hisoblanadi:

1) agar birinchi qator ikkinchisidan qisqa va birinchi qatorning barcha

belgilari ikkinchi qatorning qismi bo’lsa, ya’ni m < n, X1X2 ... Xm =

Y1Y2.... Ym (masalan, MA5K < MASKED);

2) agar birinchi qatorning navbatdagi belgii ikkinchi qatorning tegishli

belgiidan kichik bo’lsa, ya’ni ba’zi I < min (m, n) uchun X1 = Y1, X2 = Y2,..., Xi-1 = Yi-1 ligida Xi < Yi bo’lsa (masalan, DATA < FILE, READ <

RECORD).

Umuman olganda belgilar qatorini saralashda dastlab birinchi belgi

bo’yicha saralanadi. Birinchi belgilari bir xil bo’lgan qatorlar guruhi

ikkinchi belgi bo’yicha saralanadi va hokazo, ya’ni turli rangdagi kalitlar

bo’yicha saralash tamoyiliga rioya qilinadi.

Ba’zan axborot massivining yagona usulda saralanmasligi qulay

bo’ladi. Bunday vaziyat turli ilovalar kalit sifatida massiv yozuvlarining turlimaydonlaridan foydalanadigan hollarda yuzaga keladi. Ushbu ilova uchunzarur kalit bo’yicha asosiy massivni saralash har safar bevosita

ma’lumotlarga ishlov berishni boshlash oldidan amalga oshiriladi. Ishlov

berish tugallanganidan so’ng saralangan massiv yo’kotiladi. Bunda saralash

vaqti ma’lumotlarga ishlov berishning umumiq vaqti hisobiga kiritiladi.

Bir qator hollarda turli kalitlar bo’yicha saralangan massivlar yoki

fayllar KOMPYUTER xotirasida doimiy saqlanadi. Bunday massivlar

invertlangan massivlar deyiladi. Bunda xotiraning ko’p sarflanishi ko’pincha ishlov berish jarayonining tezlashishi hisobiga o’zini oqlaydi.

Saralash jarayonida foydalaniladigan texnika vositalari tarkibiga ko’ra

ichki va tashqi saralash farqlanadi. Agar tartibga solinadigan massiv

to’laligicha operativ xotirada joylashadigan va saralash jarayonida

davomida o’sha erda turadigan bo’lsa bu ichki saralash hisoblanadi. Tashqi

saralash hajmi operativ xotiraning bo’sh xotirasidan ortiq bo’lgan

ma’lumotlar massivlarida o’tkaziladi. Bu holda dastlabki va saralangan

ma’lumotlar massivlari tashqi xotira qurilmalarida joylashadi. Saralash

jarayonida dastlabki massivning bir qismi operativ xotirada o’qiladi, u erda

ichki saralsha usullaridan biri bilan saralanadi, so’ngra tashqi xotira

qurilmasiga yozib olinadi. Bu jarayon bir necha marta takrorlanadi. SHu

tariqa saralab olingan yozuvlar ketma-ketligi so’ngra birlashtiriladi. Tashqi

xotira qurilmasidagi tartibga solingan ma’lumotlar ketma-ketligini

birlashtirish operatsiyasi qo’shilish deb ataladi. SHunday qilib, tashqi

saralash ishlov berishning ikki bosqichini: ichki saralash va qo’shilishni o’z

ichiga oladi.

Ichki saralashning ko’plab usullari mavjud va ularning har biri o’z

afzalliklari va kamchiliklariga ega bo’lib, ma’lumotlar va apparaturaning

muayyan konfiguratsiyalarida boshqalaridan samaraliroq bo’lishi mumkin.

Saralash usullarining tavsiflarini baholash har bir muayyan holatda bu

usullardan birini to’g’ri tanlash imkonini beradi.

Yozuvlarning dastlabki ketma-ketligi turli darajada tartibga solingan

bo’lishi mumkin. Balki uning (yozuv) elementlari belgilangan tartibda

joylashgan bo’lishi mumkin.

Boshqa bir holatda elementlar belgilanganga teskari, ya’ni

yozuvlarning dastlabki ketma-ketligi teskari tartibda joylashgan bo’lishi

mumkin. Umuman olganda ketma-ketlik elementlari istalgan ixtiyoriy

tartibda joylashishi mumkin. YOzuvlarning dastlabki ketma-ketligining

qanday tartibda joylashganlik darajasiga ko’ra solishtirishlar va joyini

o’zgartirishlarning u yoki bu soni talab etiladi. Saralash usulini

baholashda solishtirishlar va o’rnini o’zgartirishlarning eng ko’p va kam

sonlarini topish juda oson. Bu operatsiyalarning o’rtacha sonini aniqlash

uchun kombinatorikaning tegishli bo’limlarini jalb etish zarur. Amaliyotda

usul tavsiflarining o’rtacha qiymatlarini baholash uchun bu tavsiflarning

o’rtacha arifmetik qiymatlarini arproksimatsiyalashdan foydalaniladi.

Odatda saralash S jarayonida bajariladigan solishtirish

operatsiyalarining o’rtacha soni va elementlarning o’rnini almashtirish

yoki o’zgartirishlarning o’rtacha soni turli usullarni baholash mezonlari

hisoblanadi. Saralash samaradorligi solishtirishlarning o’rtacha sonini

massiv elementlarining soniga bo’linmasi sifatida aniqlanadi.

Odatda KOMPYUTER laming operatsion tizimlari xech bo’lmaganda

bitta dastur - saralash utilitasidan iborat bo’ladi. Lekin ma’lumotlarga ishlovberishning muayyan vazifalarini hal qilishda utilita taklif etayotgan usul yaroqsiz bo’lishi va boshqa usulni ishlab chiqish yoki foydalanishga to’g’ri kelishi mumkin. SHu munosabat bilan saralashning asosiy usullarini bilash va muayyan vazifa uchun yaroqli bo’lgan u yoki bu usulni baholash olish muhimdir.