3-mavzu. Tanlash va joylashtirish turkumidagi murakkablikga ega saralash algoritmlari. Reja

3-mavzu. Tanlash va joylashtirish turkumidagi murakkablikga ega saralash algoritmlari.

Reja:

1. Saralashning asosiy tushunchalari va printsiplari

2. Ma’lumotlarning chiziqli tuzilmalarini saralashning asosiy usullari

Tayanch so’zlar: Saralash tushunchasi. Saralash algoritmlari. Tanlash va joylashtirish usulida saralash, Oʻsib borish va kamayish tartibida saralash, qoʻshish usulida saralash, Joyida abstrakt qoʻshib saralash, Yuqoridan pastga qoʻshib saralash.

1. Saralashning asosiy tushunchalari va printsiplari

Agar ma’lumotlar EX.M xotirasida muayyan tartibda saqlanadigan bo’lsa, axborotga ishlov berish va uni izlash bilan bog’liq ko’p masalalar oddiyroq, tezroq va samaraliroq xal qilinadi. Bir qator xollarda ma’lumotlarning tartibga solinganligidan foyda aniq bo’lib, 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 xar safar muayyan vazifaga nisbatan xal qilinishi zarur. Bunda tashqi xotira qurilmalari imkoniyatlari, operativ xotira xajmi, ma’lumotlarga murojaat qilish tezligi, ularni yangilab turish tezligi va ishlov berish xarakteri kabilarni taxlil qilish zarur.

Turli ilovalarda tartibga solishning turli mezonlaridan foydalaniladi. Ma’lumotlar ularga murojaat kilish extimolining kiymati, kancha tez-tez murojaat etib turilishiga kura tartibga solinishi mumkin. Odatda, tartibga solish kalit buyicha amalga oshiriladi.

Axborot tizimlari bilan ishlov beriladigan ma’lumotlar birligi bir kator axborot maydonlaridan iborat bulgan yozuv xisoblanadi. Kalit bitta yozuv maydoni ichidagi narsalar (kalit maydoni) yoki muayyan maydonlar majmuidan iborat bulishi mumkin. Keyingi xolda kalit tarkibiy deb ataladi. Yozuv fakat bitgagina maydondan iborat bulishi mumkin va bu xolda u kalitli xisoblanadi. Tartibga solishda natijasida yozuvlar kalitlarning kiymati ortib borishi yoki kamayib borish buyicha joylashadi. Bunday tartibga solish jarayoni saralash deb ataladi. Masalan, fakulьtet talabalari tugrisidagi ma’lumotlardan iborat bulgan yozuvlar talabalarning reyting daftarchalari nomerlari buyicha tartibga solingan bulishi mumkin.

Ba’zan, ayniksa, yozuvlarning kaliti tarkibiy bulgan xollarda, tartibga solingan yozuvlar ichida xam tartibga solish zarur buladi, Masalan, fakulьtetning barcha talabalari tugrisidagi yozuvlar guruxdarning ratsamlari buyicha, xar bir gurux ichida esa familiyalarning birinchi xarfi alifbo tartibida tartibga solingan bulishi mumkin. Bu xolda gurux nomeri katga, familiyaning xarfi esa kichik kalit buladi.

Umuman olganda, kalitlarning bir nechta darajalarini belgilash mumkin, bunda katta kalit birinchi rang kalit, kichik kalitlar esa tegishlicha ikkinchi, uchinchi rang kalitlari deb ataladi va xokazo. Bu xolda saralash boskichma-boskich amalga oshiriladi. Dastlab, yozuvlar massivi birinchi rang kalit buyicha saralanadi Sungra birinchi rang kalitning kiymatlari bir xil bulgan yozuvlar ikkinchi kalit rangi buyicha saralanadi va xokazo. Masalan, lugatning birinchi rang kaliti suzning birinchi xarfi, ikkinchi rang kaliti esa ikkinchi xarfi va xokazo buladi.

Saralash jarayonida yozuvlar xotirada shunday jismoniy surilishi mumkinki, bunda kichik kalitli yozuv katta kalitli yozuvdan oldinda joylashib koladi. Lekin xar doim xam jismoniy surilish sodir bulmaydi. Bir kator xollarda yordamchi jadval tuzish va uning yordamida kalitlarining tartibiga muvofik joylashgan yozuvlardan erkin foydalanish ta’minlanadi. Masalan, kursatkichlar vektoridan foydalanish mumkin, uning xar elementa yozuvning indeksi yoki manzilidan iborat buladi. Vektor elementlarining yurish tartibi asosiy massiv elementlarining tartibga solingan ketma-ketligini belgilab beradi.

Kalit maydonida sonli yoki belgili ma’lumotlar saklanishi mumkin. Kalitining xarakteriga ko’ra, yozuvlar sonli usulda yoki alifbo-raqamli usulda saralanadi. Sonli saralashda yozuvlar kalitining kiymatiga karab ortib boradigan yoki kamayib boradigan tarzda tartibga solinadi. Agar kalit maydonida belgili ma’lumotlar sakdanayotgan bulsa, saralashda belgilarning katorlari solishtiriladi. Saralash natijasida massiv yozuvlarining leksik-grafik tartibda joylashish tartibi belgilanadi. Simvollarni solishtirishda ularni mashinada takdim etishning ikkilamchi kodlari solishtiriladi. Katta kodga ega bulgan belgi katta xisoblanadi.

Ba’zan axborot massivining yagona usulda saralanmasligi kulay buladi. Bunday vaziyat turli ilovalar kalit sifatida massiv yozuvlarining turli maydonlaridan foydalanadigan xollarda yuzaga keladi. Ushbu ilova uchun zarur kalit buyicha asosiy massivni saralash xar safar bevosita ma’lumotlarga ishlov berishni boshlash oldidan amalga oshiriladi. Ishlov berish tugallanganidan sung saralangan massiv yukotiladi. Bunda saralash vakti ma’lumotlarga ishlov berishning umumiy vakti xisobiga kiritiladi.

Bir kator xollarda turli kalitlar buyicha saralangan massivlar yoki fayllar EXM xotirasida doimiy saklanadi. Bunday massivlar inverslangan (teskarilangan) massivlar deyiladi. Bunda xotiraning kup sarflanishi, kupincha, ishlov berish jarayonining tezlashishi xisobiga uzini oklaydi.

Saralash jarayonida foydalaniladigan texnika vositalari tarkibiga kura ichki va tashki saralash farklanadi. Agar tartibga solinadigan massiv tulaligicha operativ xotirada joylashadigan va saralash jarayonida davomida usha yerda turadigan bulsa, bu ichki saralash xisoblanadi. Tashki saralash xajmi operativ xotiraning bush xotirasidan ortik bulgan ma’lumotlar massivlarida utkaziladi. Bu xolda dastlabki va saralangan ma’lumotlar massivlari tashki xotira kurilmalarida joylashadi. Saralash jarayonida dastlabki massivning bir kismi operativ xotirada ukiladi, u yerda ichki saralash usullaridan biri bilan saralanadi, sungra tashki xotira kurilmasiga yozib olinadi. Bu jarayon bir necha marta takrorlanadi. Shu tarika saralab olingan yozuvlar ketma-ketligi keyinchalik birlashtiriladi. Tashki xotira kurilmasidagi tartibga solingan ma’lumotlar ketma- ketligini birlashtirish operatsiyasi kushilish deb ataladi. Shunday kilib, tashki saralash ishlov berishning ikki boskichini: ichki saralash va kushilishni uz ichiga oladi.

Ichki saralashning kuplab usullari mavjud va ularning xar biri uz afzalliklari va kamchiliklariga ega bulib, ma’lumotlar va apparaturaning muayyan konfiguratsiyalarida boshkalaridan samaralirok bulishi mumkin. Saralash usullarining tavsiflarini baxolash kar bir muayyan kolatda bu usullardan birini tugri tanlash imkonini beradi.

Yozuvlarning dastlabki ketma-ketligi turli darajada tartibga solingan bulishi mumkin. Balki yozuv elementlari belgilangan tartibda joylashgan bulishi mumkin.

Boshka bir xolatda elementlar belgilanganga teskari, ya’ni yozuvlarning dastlabki ketma-ketligi teskari tartibda joylashgan bulishi mumkin. Umuman olganda, ketma-ketlik elementlari istalgan ixtiyoriy tartibda joylashishi mumkin. Yozuvlarning dastlabki ketma-ketligining kanday tartibda joylashganlik darajasiga kura, solishtirishlar va joyini uzgartirishlarning u yoki bu soni talab etiladi. Saralash usulini bakolashda solishtirishlar va urnini uzgartirishlarning eng kup va kam sonlarini topish juda oson. Bu operatsiyalarning urtacha sonini anikdash uchun kombinatorikaning tegishli bulimlarini jalb etish zarur. Amaliyotda usul tavsiflarining urtacha kiymatlarini bakolash uchun bu tavsiflarning urtacha arifmetik kiymatlarini arproksimatsiyalashdan foydalaniladi.

Odatda, saralash jarayonida bajariladigan solishtirish operatsiyalarining urtacha soni va elementlarning urnini almashtirish yoki uzgartirishlarning urtacha soni turli usullarni baxolash mezonlari xisoblanadi. Saralash samaradorligi solishtirishlarning urtacha sonini massiv elementlarining soniga bulinmasi sifatida aniklanadi.

Odatda, EX.M larning operatsion tizimlari, xech bulmaganda, bitta dastur - saralash utilitasidan iborat buladi. Pekin ma’lumotlarga ishlov berishning muayyan vazifalarini xal kilishda utilita taklif etayotgan usul yaroksiz bulishi va boshka usulni ishlab chikish yoki foydalanishga tugri kelishi mumkin. SHu munosabat bilan saralashning asosiy usullarini bilish va muayyan vazifa uchun yarokli bulgan u yoki bu usulni baxolay olish muximdir.

2. Ma’lumotlarning chiziqli tuzilmalarini saralashning asosiy usullari

Istalgan usulda utkaziladigan saralash jarayoni bir necha tsikllardan iborat buladi. Har bir siklda yozuvlarning butun ketma-ketligi kurib chikiladi va uning elementlari bilan muayyan operatsiyalarni bajariladi. Ishlov berishning bir tsikli utish deb ataladi.

Foydalanilayotgan saralash usuliga boglik xolda tartibga solingan ketma-ketlik dastlabki ketma-ketlik joylashgan xotira uchastkasiga joylashtiriladi yoki uzi uchun xotiraning bush uchastkasini talab etadi. Biirinchi xolda usul xotira buyicha minimal xisoblanadi. Saralashning asosiy usullarini kurib chikamiz.

Tanlash usuli. Ushbu usul bilan saralashda yozuvlarning tartibga solingan ketma-ketligi xotiraning dastlabki ketma-ketlik joylashgan uchastkasining uzida tashkil etiladi. Birinchi utish davomida eng kichik element izlanadi. Bu element topilganidan sung uni dastlabki ketma-ketlikdagi birinchi element bilan joyi almashtiriladi, natijada eng kichik element tuzilayotgan tartibga solingan ketma-ketlikda birinchi xolatni egallaydi. Sungra kolgan elementlar ichidan keyingi eng kichik element izlanadi. Topilgan bu element xam dastlabki ketma-ketlikning ikkinchi elementi bilan joyi almashtiriladi. Ikkinchi utishdan sung ikki elementdan iborat bulgan ketma-ketlik tuzilgan buladi, ulardan birinchisi ikkinchisidan kichik buladi. Kalitining kiymati eng kichik bulgan keyingi elementni izlash va uni dastlabki ketma-ketlikning tegishli pozitsiyalariga joylashtirish barcha elementlar oshib boruvchi tartibda saralanib bulingunga kadar davom etadi.

Tanlash usuli bilan saralash namunasi quyidagi rasmda keltirilgan. Saralash usullarini rasmlarda kursatishda yozuvlar fakat kalit maydonidan iborat deb kuzda tutiladi,

ya’ni tartibga solinayotgan ketma-ketlik elementlari yozuvlar kalitining kiymatlari xisoblanadi. 10.1-rasmda belgilangan rakamlar ushbu utishda kalitining eng kichik kiymati buyicha tanlab olingan yozuvlarni bildiradi. Ushbu utish uchun kushalok chizikdan chapda joylashgan elementlar tartib buyicha kuyilgandir. 6 ta elementdan iborat bulgan yozuvlarning A ketma-ketligi besh utishda saralanibbuldi.Ushbuusulningtavsiflarinibaxolaymiz. N elementdan iborat ketma-ketlikni saralash uchun N - 1 utish talab etiladi, chunki xar bir utishda tartibga solingan ketma-ketlikning xar bir tegishli fakat bitta element kiritiladi. I - utish uchun N - i solishtirish talab etiladi. Demak, solishtirishlarning umumiy soni

Yukorida kurib chikilgan usul bilan saralashda solishtirishlar soni dastlabki ketma-ketlikning tartibga solinganlik darajasiga boglik bulmaydi. SHuning uchun olingan ifoda solishtirishlarning eng kam, eng kup va urtacha sonini anikdaydi. Solishtirishlarning urtacha sonini baxolash uchun ifodalarning kuyidagi approksimatsiyasidan foydalanish mumkin (1): 0,5 N². Bunday approksimatsiya N = 100 ligida 1 % va N = 1000 ligida 0,1 % xatolikka yul kuyishi mumkin. Tanlash usuli bilan saralashda solishtirishlarning urtacha soni 0,5№ ga mutanosib deb xisoblash mumkin.

Elementlarning joyini almashtirish mikdori dastlabki ketma-ketlik elementlarining joylashuviga boglikdir. Lekin istalgan xolda xam bitta utish davomida bittadan ortik bulmagan joy almashtirish talab etiladi; demak joy almashtirishlarning eng kup soni N-1 ga teng. Eng yaxshi xolda, ya’ni dastlabki ketma-ketlik tartibga solingan bulsa bitta xam joy almashtirish talab etilmaydi. Demak, joy almashtirishlar urtacha soni N/2 ga mutanosibdir.