Ўзбекистон республикаси олий ва ўрта махсус таълим вазирлиги фарғона давлат университети


I. BOB. MASSIVLAR HAQIDA UMUMIY MA’LUMOT


Download 1.2 Mb.
bet2/2
Sana08.10.2020
Hajmi1.2 Mb.
#132947
1   2
Bog'liq
Mamadvaliyeva Mahfuza Kurs ishi algoritmlar nazariyasi 1

I. BOB. MASSIVLAR HAQIDA UMUMIY MA’LUMOT


Massiv deb –bir nom bilan murojaat qilish mumkin bo‘lgan bitta tipga tegishli indekslangan o‘zgaruvchilar to‘plamidir. C # da massivlar bir o'lchovli yoki ko'p o'lchovli bo'lishi mumkin. Ko‘p hollarda bir o‘lchovli massivlardan foydalaniladi. Massivlar turli maqsadlarga xizmat qiladi. Ular o‘zgaruvchilarni birbiriga bog'lash uchun qulay vositalarni ta'minlaydi.Masalan, siz massivda saqlashingiz mumkin maksimal kunlik haroratni qayd etib borishni, bir oy ichida birja kurslari ro'yxati yoki uy kutubxonasidagi dasturiy kitoblarning nomlarini.

Massivning asosiy afzalligi ma'lumotlarni tashkillashtirishdadir shuning uchun ularni manipulyatsiya qilish osonroq hisoblanadi. Shunday qilib, agar ma'lum bir aktsiyalar guruhiga to'langan dividendlarni o'z ichiga olgan qator mavjud bo'lsa, ushbu qator elementlariga siklik kirish va aktsiyalarning o'rtacha daromadini hisoblashni tashkil etishni osonlikcha massivlarda amalga oshira olasiz. Bunga qo'shimcha ravishda, massivlar ma'lumotlarni osongina tartibga solishga imkon beradi. Boshqa dasturlash tillarida bo‘lgani kabi C # dasturlash tilida ham massivlaridan shunday qo‘llaniladi.Shunga qaramasdan ularning bitta xususiyati bor: massivlarni obyekt shaklida ham amalga oshirish mumkin.



Ob'ektlar shaklida massivlarni amalga oshirishda bir qator muhim afzalliklarni beradi va oxirgilaridan ancha yirigi, "to‘plash" yordamida ishlatilmagan qatorlarni yo'q qilish qobiliyatiga egadir.C# da massivlar boshqa C dasturlash tillaridagi massivlardan ancha farq qiladi. Buni misollar yordamida ko‘rib o‘tamiz.

nt [] k ; // k – massiv.

K = new int [3] ; // massiv 3 ta int tipiga tegishli elementdan iborat.

K [0] = -5 ; K [1] = 4 ; K [2] = 1; // massiv elementlarini e‘lon qilamiz. // massivning uchinchi elementini chiqaramiz.

Console.Writeline(k[2]+‖‖);

Yuqoridagilardan ko‘rinib turibdiki, massiv quyidagicha e‘lon qilinadi :

Int [] k;

Quyidagisi esa xato hisoblanadi: int k[]; //xato! int k []; //xato!



Misol:

using System;

using System.Text;

namespace massiv

{

class Program

{

public static void Main(string[] args)

{

int s = 0; int[] a = new int[5];

a[0] = 6; a[1] = 3;

a[2] = 7; a[3] = 5; a[4] = 2;

s=a[0]+a[1]+a[2]+a[3]+a[4];

Console.Write("s="+s);

Console.ReadKey();

}

}

}




1.1-rasm.

Misol:


using System;

using System.Text;

namespace massiv

{

class Program

{

static void Main(string[] args)

{

int s = 0; int[] a = {2,3,4,5,6};

s=a[0]+a[1]+a[2]+a[3]+a[4];

Console.Write("s="+s);

Console.ReadKey();

}

}

}


2.2-rasm.

1.2 Bir o`lchovli massivlar


Kompyuterdan foydalanishning asosiy yo`nalishlaridan biri bu ma`lumotlarni to`plash va qayta ishlashdir - turli jadvallar, kataloglar, lug`atlar va boshqa ma`lumotlar. Bunday ma`lumotlarni dasturda aks ettirish uchun massivlardan foydalanish qulay. Qoida tariqasida, bunday ma`lumotlarni qayta ishlash xuddi shu qonunga muvofiq amalga oshiriladi, buning uchun siklik algoritmlardan foydalanish qulay. Massivning har bir alohida tarkibiy qismi element deb ataladi. Elementlar soniga massivning kattaligi deyiladi. Elementlar turi qator turini aniqlaydi. Massivning o`lchami va turi uning tavsifida ko`rsatiladi va o`lcham malum qiymat yoki oldindan belgilangan doimiy tomonidan ko`rsatilishi mumkin. Element raqami indeks deb ataladi. Indekslar musbat doimiy yoki butun o`zgaruvchilar bo`lishi mumkin. Massivning ba`zi elementlariga murojaat qilish uchun, elementning indeksini yonidagi qavs ichida element indeksini ko`rsatish kerak. Ammo ko`pincha ma`lumotlar jadval (matritsa) shaklida tashkil etilishi mumkin, bu yerda har bir o`zgaruvchining joylashishi qator raqami va ustun raqami bilan belgilanadi. Masalan, auditoriya ichidagi joy qatorning raqamini va ushbu qatordagi orindiqlar sonini ko`rsatib belgilanadi. Bunday ma`lumotlarni ikki o`lchovli qator sifatida tavsiflash qulay. Bir olchovli qatordan farqli olaroq, ikki o`lchovli massivning har bir elementi indekslar juftiga mos keladi. Birinchi indeks qator raqami, ikkinchisi esa qator elementi joylashgan ustun raqami.

Mаssiv elеmеntlаri аvvаldаn tаyyor bеrilgаn vа dаstlаbki kеtmа-kеtliklаrgа bo`linаdi. I=2 dаn bоshlаb, hаr bir qаdаmdа dаstlаbki kеtmа -kеtlikdаn I-elеmеnt chiqаrib оlinаdi hаmdа tаyyor kеtmа-kеtlikning kеrаkli o`rnigа kiritib qo`yilаdi. Kеyin I bittаgа ko`pаyadi vа h.k.



Tаyyor dаstlаbki kеtmа-kеtlik

Kеrаkli jоyni izlаsh jаrаyonidа, ko`prоq ongdаn bittа pоzitsiyadаn tаnlаb оlingаn elеmеntni uzаtish аmаlgа оshirilаdi, yani tаnlаb оlingаn elеmеnt, J:=I-1 dаn bоshlаb, turlаrgа аjrаtib bo`lingаn qismning nаvbаtdаgi elеmеnti bilаn qiyoslаnаdi. Аgаr tаnlаb оlingаn elеmеnt а[I] dаn kаttа bo`lsа, uni turlаrgа аjrаtish qismigа qo`shаdilаr, аks hоldа a[J] bittа pоzitsiyagа surilаdi, tаnlаb оlingаn elеmеntni esа turlаrgа аjrаtilgаn kеtmа-kеtlikning nаvbаtdаgi elеmеnti bilаn qiyoslаydilаr. To`g`ri kеlаdigаn jоyni qidirish jаrаyoni ikkitа turlichа shаrt bilаn tugаllаnаdi:


- аgаr a[J]>a[I] elеmеnti tоpilgаn bo`lsа;

- аgаr tаyyor kеtmа-kеtlikning chаp uchigа yеtilgаn bo`lsа.

int i, j, x;

fjr(i=1; i

{

x=[i];// kiritib qo`shishimiz lоzim bo`lgаn elеmеntni esdа sаqlаb qоlаmiz



j=i-1;

while(x=0)//to`g`ri kеlаdigаn jоyni qidirish

}

a[j+1]=a[j]$//o`ngа surilish



j--;

{

a[j+1]=x;//elеmеntni kiritish



}

II. BOB. ALGORITMLAR HAQIDA TUSHUNCHA. MASSIVLARNI SARALASH ALGORITMLARI

2.1 Algoritmning asosiy xossalari.


Algoritmning 5 ta asosiy xossasi bor:

Diskretlilik (Cheklilik). Bu xossaning mazmuni algoritmlarni doimo chekli qadamlardan iborat qilib bo‘laklash imkoniyati mavjudligida. Ya’ni uni chekli sondagi oddiy ko‘rsatmalar ketma-ketligi shaklida ifodalash mumkin. Agar kuzatilayotgan jarayonni chekli qadamlardan iborat qilib qo‘llay olmasak, uni algoritm deb bo‘lmaydi.



Tushunarlilik. Biz kundalik hayotimizda berilgan algoritmlar bilan ishlayotgan elektron soatlar, mashinalar, dastgohlar, kompyuterlar, turli avtomatik va mexanik qurilmalarni kuzatamiz. Ijrochiga tavsiya etilayotgan ko‘rsatmalar, uning uchun tushinarli mazmunda bo‘lishi shart, aks holda ijrochi oddiygina amalni ham bajara olmaydi. Undan tashqari, ijrochi har qanday amalni bajara olmasligi ham mumkin.Har bir ijrochining bajarishi mumkin bo‘lgan ko‘rsatmalar yoki buyruqlar majmuasi mavjud, u ijrochining ko‘rsatmalar tizimi (sistemasi) deyiladi. Demak, ijrochi uchun berilayotgan har bir ko‘rsatma ijrochining ko‘rsatmalar tizimiga mansub bo‘lishi lozim.Ko‘rsatmalarni ijrochining ko‘rsatmalar tizimiga tegishli bo‘ladigan qilib ifodalay bilishimiz muhim ahamiyatga ega. Masalan, quyi sinfning a’lochi o‘quvchisi "son kvadratga oshirilsin" degan ko‘rsatmani tushinmasligi natijasida bajara olmaydi, lekin "son o‘zini o‘ziga ko‘paytirilsin" shaklidagi ko‘rsatmani bemalol bajaradi, chunki u ko‘rsatma mazmunidan ko‘paytirish amalini bajarish kerakligini anglaydi.

Aniqlik. Ijrochiga berilayotgan ko‘rsatmalar aniq mazmunda bo‘lishi zarur. Chunki ko‘rsatmadagi noaniqliklar mo‘ljaldagi maqsadga erishishga olib kelmaydi. Odam uchun tushinarli bo‘lgan "3-4 marta silkitilsin", "5-10 daqiqa qizdirilsin", "1-2 qoshiq solinsin", "tenglamalardan biri yechilsin" kabi noaniq ko‘rsatmalar robot yoki kompyuterni qiyin ahvolga solib qo‘yadi. Bundan tashqari, ko‘rsatmalarning qaysi ketma-ketlikda bajarilishi ham muhim ahamiyatga ega. Demak, ko‘rsatmalar aniq berilishi va faqat algoritmda ko‘rsatilgan tartibda bajarilishi shart ekan.

Ommaviylik. Har bir algoritm mazmuniga ko‘ra bir turdagi masalalarning barchasi uchun ham o‘rinli bo‘lishi kerak. Ya’ni masaladagi boshlang‘ich ma’lumotlar qanday bo‘lishidan qat’iy nazar algorim shu xildagi har qanday masalani yechishga yaroqli bo‘lishi kerak. Masalan, ikki oddiy kasrning umumiy mahrajini topish algoritmi, kasrlarni turlicha o‘zgartirib bersangiz ham ularning umumiy mahrajlarini aniqlab beraveradi. Yoki uchburchakning yuzini topish algoritmi, uchburchakning qanday bo‘lishidan qat’iy nazar, uning yuzini hisoblab beraveradi.

Natijaviylik. Har bir algoritm chekli sondagi qadamlardan so‘ng albatta natija berishi shart. Bajariladigan amallar ko‘p bo‘lsa ham baribir natijaga olib kelishi kerak. Chekli qadamdan so‘ng qo‘yilgan masala yechimga ega emasligini aniqlash ham natija hisoblanadi. Agar ko‘rilayotgan jarayon cheksiz davom etib natija bermasa, uni algoritm deb atay olmaymiz.



Yuqorida ko‘rilgan misollarda odatda biz masalani yechish algoritmini so‘zlar va matematik formulalar orqali ifodaladik. Lekin algoritm boshqa ko‘rinishlarda ham berilishi mumkin. Biz endi algoritmlarning eng ko‘p uchraydigan turlari bilan tanishamiz.

Algoritmning so‘zlar orqali ifodalanishi. Bu usulda ijrochi uchun beriladigan har bir ko‘rsatma jumlalar, so‘zlar orqali buyruq shaklida beriladi. Algoritmning formulalar bilan berilish usulidan matematika, fizika, kimyo kabi aniq fanlardagi formulalarni o‘rganishda foydalaniladi. Bu usulni ba’zan analitik ifodalash deyiladi.

Algoritmlarning grafik shaklida tasvirlanishida algoritmlar maxsus geometrik figuralar yordamida tasvirlanadi va bu grafik ko‘rinishi blok-sxema deyiladi.

Algoritmning jadval ko‘rinishda berilishi. Algoritmning bu tarzda tasvirlanishdan ham ko‘p foydalanamiz. Masalan, maktabda qo‘llanib kelinayotgan to‘rt xonali matematik jadvallar yoki turli xil lotereyalar jadvallari. Funksiyalarning grafiklarini chizishda ham algoritmlarning qiymatlari jadvali ko‘rinishlaridan foydalanamiz. Bu kabi jadvallardan foydalanish algoritmlari sodda bo‘lgan tufayli ularni o‘zlashtirib olish oson.



Blok-sxemalarni tuzishda foydalaniladigan asosiy sodda geometrik figuralar quyidagilardan iborat:

1-jadval.




Nоmi

Bеlgilаnishi

Bаjаrаdigаn vаzifаsi

Jаrаyon




Bir yoki bir nеchtа аmаllаrni

bаjаrilishi nаtijаsidа

mа’lumоtlаrning uzgаrishi



Qаrоr




Birоr shаrtgа bоglik rаvishdа

аlgоritmning bаjаrilish yunаlishini

tаnlаsh


SHаkl

O'zgаrtirish






Dаsturni uzgаrtiruvchi buyruk yoki

buyruklаr turkumini uzgаrtirish

аmаlini bаjаrish


Аvvаl

Аniqlаngаn

jarayon





Оldindаn ishlаb chikilgаn dаstur

yoki аlgоritmdаn fоydаlаnish



Kiritish chiqarish




Ахbоrоtlаrni kаytа ishlаsh mumkin

bulgаn shаklgа utkаzish yoki оlingаn

nаtijаni tаsvirlаsh


Xujjat




Ахbоrоtlаrni kоgоzgа chikаrish yoki

kоgоzdаn kiritish



Axborot oqimi chizig’i




Blоklаr оrаsidаgi bоglаnishlаrni

Tаsvirlаsh



Bog’lagich




Uzilib kоlgаn ахbоrоt оkimlаrini

ulаsh bеlgisi



Boshlash tugatish




Ахbоrоtni kаytа ishlаshni bоshlаsh,

vаktinchа yoki butunlаy tuхtаtish



Izoh




Blоklаrgа tеgishli turli хildаgi

Tushuntirishlаr


Blok-sxemalar bilan ishlashni yaxshilab o‘zlashtirib olish zarur, chunki bu usul algoritmlarni ifodalashning qulay vositalaridan biri bo‘lib programma tuzishni osonlashtiradi, programmalash qobiliyatini mustahkamlaydi. Algoritmik tillarda blok - sxemaning asosiy strukturalariga maxsus operatorlar mos keladi.

Shuni aytish keraki, blok-sxemalardagi yozuvlar odatdagi yozuvlardan katta farq qilmaydi.

Misol:




Amal

Amal

Amal

Chiziqli algoritmlar. Har qanday murakkab algoritmni ham uchta asosiy struktura yordamida tasvirlash mumkin. Bular ketma-ketlik, ayri va takrorlash strukturalaridir. Bu strukturalar asosida chiziqli, tarmoqlanuvchi va takrorlanuvchi hisoblash jarayonlarining algoritmlarini tuzish mumkin. Umuman olganda, algoritmlarni shartli ravishda quyidagi turlarga ajratish mumkin:

chiziqli algoritmlar;

tarmoqlanuvchi algoritmlar;

takrorlanuvchi yoki siklik algoritmlar;

ichma-ich joylashgan siklik algoritmlar;

rekurrent algoritmlar;

takrorlanishlar soni oldindan no’malum algoritmlar;



ketma-ket yaqinlashuvchi algoritmlar.

Faqat ketma-ket bajariladigan amallardan tashkil topgan algoritmlarga-chiziqli algoritmlar deyiladi. Bunday algoritmni ifodalash uchun ketma-ketlik strukturasi ishlatiladi. Strukturada bajariladigan amal mos keluvchi shakl bilan ko‘rsatiladi. Chiziqli algoritmlar blok-sxemasining umumiy strukturasini quyidagi ko‘rinishda ifodalash mumkin:




1-amal

2-amal

n-amal

Shu blok sxema orqali har qanday masalani yechish mumkin.


2.2 Massivlarni tezkor saralash.


Ichki saralash modeli. Ma’lumotlar EHM xotirasida muayyan tartibda saqlanadigan bo‘lsa, axborotga ishlov berish va uni izlash bilan bog‘liq ko‘p masalalar oddiyroq, tezroq va samaraliroq hal qilinadi. Bir qator hollarda 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 tartiblash 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 beradigan ma’lumotlar birligi bir qator axborot maydonlaridan iborat bo‘lgan yozuv hisoblanadi. Kalit bitta yozuv maydoni ichidagi yoki muayyan maydonlar majmuidan iborat bo‘lishi mumkin. Keyingi holda kalit tarkibiy deb ataladi. YOzuv faqat bittagina maydondan iborat bo‘lishi mumkin va bu holda u kalitli hisoblanadi. Tartibga solish natijasida yozuvlar kalitlarning qiymati ortib borishi yoki kamayib borish bo‘yicha joylashadi. Bunday tartibga solish jarayoni tartiblash deb ataladi. Masalan, fakultet talabalari to‘g‘risidagi ma’lumotlardan iborat bo‘lgan yozuvlar talabalarning reyting daftarchalari nomerlari bo‘yicha tartibga solingan bo‘lishi mumkin.

Ichki tartiblashning ko‘plab usullari mavjud va ularning har biri o‘z afzalli texnikalari va texnik kamchiliklariga ega bo‘lib, ma’lumotlar va apparaturaning muayyan konfigurasiyalarida boshqalaridan samaraliroq bo‘lishi mumkin ekan. Tartiblash usullarining tavsiflarini baholash har bir muayyan holatda bu usullardan birini to‘g‘ri tanlash texnik imkonini beradi.



Saralashning sodda sxemalari. Eng sodda tartiblash usullaridan biri bo‘lib

«pufakcha» usuli hisoblanadi. Bu algoritmning asosiy g‘oyasini yozish uchun tartiblanishi kerak bo‘lgan yozuvlar vertikal joylashgan massivda saqlanadi deb faraz qilamiz. Kalit maydonning kichik qiymatli yozuvlari «yengil» va shuning uchun pufakcha kabi ular yuqoriga «suzib chiqadi». Massiv bo‘ylab birinchi o‘tishda massivning birinchi yozuvi olinadi va uning kaliti navbatma-navbat keyingi yozuvlarning kalitlari bilan solishtirib boriladi. Agar nisbatan «og‘ir» kalitli yozuvlar uchrasa, u holda bu yozuvlar joyini almashtiradi. Nisbatan «yengil» yozuvlar uchraganda bu yozuv taqqoslash uchun etolon bo‘ladi va keyingi barcha yozuvlar shu kalit bilan solishtiriladi. Natijada eng kichik qiymatli kalit massivning eng yuqorisiga chiqadi. Massiv bo‘ylab ikkinchi o‘tishda massivning massivni birinchi o‘tishda topilgan yozuvdan keyin joylashgan og‘irligi bo‘yicha ikkinchi kalit olinadi. Massiv bo‘ylab ikkinchi va keyingi o‘tishlarda oldingi o‘tishlarda topilgan yozuvlarni ko‘rib chiqish shart emas, chunki ular qolgan yozuvlarga qaraganda kichik kalitlarga ega.

Boshqacha qilib aytganda, t – o‘tishda i pozitsiya yuqorida turgan elementlar tekshirilmaydi. 1-Dasturda ushbu algoritm keltirilgan.

«pufakcha» algoritmi



  1. for i:= I to n - 1 do

  2. for j:= 1 downto i + 1 do

  3. if A[j].key < A[j - 1].key then (4) swap(A[j], A[j - 1])

swap protsedurasi yozuvlarning o‘rnini almashtirish uchun ko‘plab tartiblash

algoritmlarida ishlatiladi, uning kodi quyidagi dasturda keltirilgan.

Yuqoridagi dasturda swap protsedurasi procedure swap ( var x, u: recordtype ) {swap x va u yozuvlarning o‘rnini almashtiradi} var temp: recordtype; begin temp:= x; x:= y; y:= temp; end; { swap }

Tez saralash. O(n log n) vaqtda bajariladigan, ichki saralash usullarining eng samaradori bo‘lib hisoblangan tez tartiblashni ko‘rib chiqamiz. Bu algoritmda massivning A[1],...,A[n] elementlarini tartiblash uchun bu elementlardan massiv elementlari unga nisbatan tartiblanadigan tayanch element sifatida v kalitning qandaydir qiymati tanlanadi. Qulaylik uchun, tayanch element sifatida kalit qiymatlari taqsimotining medianaga eng yaqin bo‘lganini tanlab olish zarur. Chunki, tayanch element kalit qiymatlarini deyarli teng ikki qismga ajratadi.

Keyin massiv elementlari shunday joylashtiriladiki, qandaydir j indeks uchun barcha A[1], ..., A[j] keltirilgan elementlar υ dan kichik kalit qiymatlarga, A[j+1], ...,



A[n] barcha elementlari υ ga teng yoki katta kalit qiymatlarga ega bo‘ladi. Keyin tez tartiblash protsedurasi A[1], .... A[j] va A[j+1], ..., A[n] elementlar to‘plamiga bu to‘plamlarni alohida tartiblash uchun rekursiv ishlatiladi. Birinchi to‘plamning kalit qiymatlari ikkinchi to‘plamning kalit qiymatlaridan kichik bo‘lgani uchun boshlang‘ich massiv to‘g‘ri tartiblanadi.



2.2 1-rasm. Tez tartiblash algoritmi etaplari.

Misol. 2.2 1-rasmda 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 butun sonlar ketma-ketligi ustida bajariladigan tez tartiblash algoritmining bajarilish qadamlari keltirilgan. Har bir qadamda υ ning qiymati eng chapdagi turli xil ikkita element-sonning kattasi sifatida tanlanadi. Tartiblash protsedurani rekursiv chaqirish jarayonida alohida qism to‘plamlar bir xil kalitdan tashkil topganda tugatiladi. 2.2 1-rasmda har bir etap ikki qadamda ko‘rsatilgan: avval har bir alohida qism to‘plam uchun o‘zining qiymati tanlanadi va keyin bu qism to‘plamning elementlari tanlangan qiymatga mos ravishda joylashtiriladi, va xuddi shunday tartiblash protsedurasi rekursiv ishlatiladigan yana ikkita qism to‘plamga bo‘linadi.

Endi quicksort protsedurasidan tashqarida aniqlangan A massiv elementlari bilan ishlaydigan quicksort rekursiv protsedurasini ishlab chiqishni boshlaymiz. Quicksort(i,j) protsedurasi A[1], ..., A[n] elementlarni tartiblashi kerak. Bu protseduraning algoritmi 2-dasturda kiritilgan.

2-dastur. Tez tartiblash usuli protsedurasi



  1. if A[i], ..., A[j] ikkita turli xil kalitlarga ega bo‘lsa then begin

  2. v — topilgan ikkita turli xil kalitlarning kattasi bo‘lsin;

  3. A[x], ..., A[j] elementlar shunday joylashtiriladiki, qandaydir k, i+l

  4. quicksort{i, k-1) ,- (5) quicksort{k, j) end

Endi tez tartiblash algoritmining eskizini (2-dastur) haqiqiy quicksort dasturiga aylantiramiz. Bu dasturning kodi 3-dasturda keltirilgan. aggau[1..n] of recordtype turidagi A massivni saralash uchun quicksort(l, n) protsedurasini chaqirish kerak.

3-dastur. Tez tartiblash usuli protsedurasi procedure quicksort (i, j: integer);

{A tashqi massivning A[i],...,A[j] elementlarini tartiblaydi} var pivot: keytype; pivotindex: integer;

{kaliti pivot ga teng bo‘lgan A massiv elementi} k: integer;

{kalit>pivot bo‘lgan elementlar guruhining boshlang‘ich indeksi} begin


  1. pivotindex:= findpivot{i, j) ;

  2. if pivotindex <> 0 then begin

{agar barcha kalitlar teng bo‘lsa, hech narsa bajarish kerak emas}

  1. pivot:= Alpivotindex] .key;

  2. k:= portition(i, j, pivot);

  3. quicksortd, k-1) ;

  4. quicksort{k, j) end end; {quicksort}

CHo‘ntak” saralash. Ko‘p hollarda O(n log n) dan kam bo‘lgan tartiblash vaqtini olish mumkin, lekin tartiblanayotgan kalitlar haqida qo‘shimcha ma’lumot kerak bo‘ladi.

4-misol. Faraz qilamiz, kalit qiymatlar 1 dan to n gacha bo‘lgan butun sonlar bo‘lib hisoblansin, ular takrorlanmaydi va tartiblanayotgan elementlar soni ham n ga teng. Agar A va V orqali aggau[1..n] of recordtype massivni ifodalansa, tartiblanishi kerak bo‘lgan n ta element birinchi A massivda joylashadi, u holda V massivga kalitlarni quyidagi qiymatlarda navbatma-navbat joylashtirib borishni tashkillashtirish mumkin:

for i:= 1 to n do

V[A[i].key]:= A[i]; (4)

Bu kod A[i] element V massivning qaerida joylashishini hisoblab beradi. Butun bir sikl O(n) vaqt tartibiga ega va barcha kalitlar qiymatlari turli xil bo‘lganda va 1 dan to n intervaldagi butun sonlar bo‘lganda yaxshi ishlaydi.

O(n) vaqtda A massiv elementlarini, lekin ikkinchi V massivni ishlatmasdan tartiblaydigan boshqa usullar ham mavjud. Navbatma-navbat A[1], ..., A[n] elementlarga murojaat qilamiz. Agar A[i] yacheyka j kalitga ega bo‘lsa va j≠i bo‘lsa, u holda A[i] va A[j] yacheykalardagi yozuvlar o‘rnini almashtiradi. Agar bu almashtirishdan keyin A[i] yacheyka k kalitga ega bo‘lsa va k≠i bo‘lsa, u holda A[i] va A[k] orasida o‘rin almashtirishlar bo‘ladi va h.k. Har bir o‘rin almashtirish hech bo‘lmaganda bitta yozuvni kerakli tartibda joylashtiradi. SHuning uchun A massiv elementlarini tartiblaydigan ushbu algoritm O(n) bajarilish vaqtiga ega bo‘ladi.

for i:= 1 to n do while A[i].key <> i do swap(A[i], A[A[i].key]); (4) dastur — bu «cho‘ntak» saralashga oddiy misol, bu erda aniqlangan qiymatli kalitlarni saqlash uchun «cho‘ntak» lar ishlatadi. Berilgan yozuv r qiymatli kalitga ega bo‘lsa, u holda bu yozuvni yozuvlar uchun «cho‘ntak»ga joylashtiramiz. Dasturda (4) «cho‘ntak» bo‘lib V massivning elementlari hisoblanadi, bu erda B[i]

– i qiymatli kalitga ega bo‘lgan yozuvlar uchun «cho‘ntak». «Cho‘ntak» sifatidagi massivlarin faqat oddiy hollarda ishlatish mumkin (bitta «cho‘ntak»da bittadan ortiq yozuv bo‘lmagan taqdirda). Bundan tashqari, massivlarni «cho‘ntak» lar sifatida ishlatishda «cho‘ntak» ichida elementlarni tartiblash zaruriyati paydo bo‘lmaydi, chunki bitta «cho‘ntak» bittadan ko‘p bo‘lmagan yozuvdan iborat, algoritm shunday yaratilganki, massivdagi elementlar to‘g‘ri tartibda joylashadi.

Lekin umumiy holda bitta «cho‘ntak» da bir nechta yozuvlarni saqlash, shuningdek bir nechta «cho‘ntak»larni bittaga birlashtirish mumkinligini e’tiborga olish kerak. Aniqlik uchun A massiv elementlari recordtype ma’lumotlar turiga, yozuv kalitlari esa – keytype turiga ega deb hisoblaymiz. recordtype turidagi ro‘yxat elementlarini listtype (ro‘yxat turi) ma’lumotlar turi orqali ifodalab olamiz. Listtype turi ro‘yxatning ixtiyoriy turi bo‘lishi mumkin, lekin hozirgi holatda bizga ko‘proq bog‘langan ro‘yxatlar to‘g‘ri keladi. Ro‘yxatning umumiy uzunligi fiksirlangan va n ga teng deb faraq qilishimiz mumkin.

Shuningdek array[keytype] of listtype turidagi V massiv ham kerak. Bu ro‘yxatlarni saqlovchi massiv «cho‘ntak»i bo‘lib hisoblanadi. V massivning indeksi keytype ma’lumotlar turiga ega, chunki bu massivning har bir elementi kalitning bitta qiymatiga mos keladi. SHunday qilib, 9-dasturni umumlashtirish mumkin, chunki endi «cho‘ntak»lar keraklicha hajmga ega. «Cho‘ntak»larni qanday birlashtirish mumkinligini ko‘rib chiqamiz. a1, a2, .... ai va b1, b2, … bj ro‘yxatlar ustida ro‘yxatlar konkatenatsiyasi operatsiyasini bajarish kerak, natijada a1, a2, .... ai i b1, b2, … bj ro‘yxatga ega bo‘lamiz. L1L2, ro‘yxatlarning birlashmasidan hosil bo‘lgan L1 ro‘yxatni egallovchi konkatenatsiya CONCATENATED(L1, L2) operatsiyasini tadbiq etish uchun ro‘yxatlarning ixtiyoriy ifodalanishidan foydalanish mumkin.

Ro‘yxat sarlavhalariga qo‘shishda konkatenatsiya operatori yanada samarali bajarilishi uchun ro‘yxatning oxirgi elementlariga ko‘rsatkichlarni ishlatish mumkin.

2.2 2-rasmda Punktir chiziqlar bilan L1 i L2 ro‘yxatlarni bitta L1 ro‘yxatga konkatenatsiyasida o‘zgargan ko‘rsatkichlar ko‘rsatilgan.

Endi yozuvlarning «cho‘ntak» saralashining dasturin tuzsak bo‘ladi. Bu dastur

5-dasturda ko‘rsatilgan, dastur ro‘yxatlar ustida bajariladigan bazaviy operatorlarni ishlatib tuzilgan.

5-dastur. binsort dasturi (cho‘ntak saralash) procedure binsort;

{A massiv elementlarini tartiblaydi, tartiblangan ro‘yxatni V[lowkey]

«cho‘ntak»ga yozadi} var i: integer; v: keytype; begin

{"cho‘ntak"ka yozuvlarni kiritish boshlanadi}



  1. for i:= 1 to n do

{ A[i] elementni «cho‘ntak» boshiga joylashtirish}

  1. INSERT(A[i], FIRST(B[A[i].key]), B[A[i].key]);

  2. for v:= succ(lowkey) to highkey do (4) CONCATENATE(B[lowkey] , B[v]) end; { binsort }





2.2 2-rasm. Bog‘langan ro‘yxatlar konkatenatsiyasi

Taqqoslanma saralashlarning bajarilish vaqtlari. Qo‘yish usuli. Agar ichki siklga qarasak yozuvlarning tartiblangan qismiga qo‘shilgan element qolgan elementlardan kichik bo‘lsa operasiyalar eng ko‘p bajariladi. Bu holda location o‘zgaruvchisi 0 ga teng bo‘lganda sikl o‘z ishini tugatadi. SHuning uchun yangi element massiv boshiga qo‘shilganda algoritm eng ko‘p bajariladi. Bunday holat joriy massivning elementlari kamayish tartibida joylashgan bo‘lsa bo‘lishi mumkin. Bu yomon holatlardan biridir.

Bunday massivni qayta ishlash jarayoni qanday bo‘lishini ko‘rib chiqamiz. Birinchi massivning ikkinchi elementi qo‘yiladi. U faqat bitta element bilan solishtiriladi. Ikkinchi qo‘yiladigan element (tartib buyicha uchinchi) oldingi ikkita element bilan, uchinchi qo‘yilgan element oldingi uchta element bilan solishtiriladi. Umuman olganda i - qo‘yiladigan element oldingi i ta element bilan solishtiriladi va bu jarayon N-1 marta takrorlanadi.


2.3 Massivlarni birlashtirib saralash algoritmi


Birlashmali saralash (Merge Sort) algoritmi asosiy beshta saralash algoritmlari (pufakchali saralash, tezkor saralash va boshqalar) dan biri bo`lib, chiziqli saralash algoritmlaridan farqli ravishda "bo`lib tashla va hukmronlik qil" tipidagi algoritm hisoblanadi.

Bu tipdagi algoritmlar katta hajmdagi masalalarni nisbatan kichik bo`lgan va oson yechiladigan qismlarga ajratgan holda bajaradi. Bunday algoritmlar masalalarni hal qilishda vaqtdan katta yutuq qilish imkonini beradi.

Birlashmali saralashda biz berilgan massivni uzunligi faqat 1 elementga teng bo`lgan qismlar qolmaguncha o`rtasidan ajratamiz. Keyin bu qismlar to`g`ri tartibda birlashtiriladi.

using System;

namespace Asosiy

{

    class Program



    {

        static void Main(string[] args)

        {

            Console.WriteLine("Nechta harflarni saralaymiz?");

            int N = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine("Saralanishi kerak bo'lgan harflarni kiriting:");

            char[] mas=new char[N];

            for (int i = 0; i < mas.Length; i++)

            {

                mas[i] = Convert.ToChar(Console.ReadLine());

            }

           char temp;

            for (int i = 0; i < mas.Length; i++)

            {

                for (int j = i + 1; j < mas.Length; j++)

                {

                    if (mas[i] > mas[j])

                    {

                        temp = mas[i];

                        mas[i] = mas[j];

                        mas[j] = temp;

                    }                   

                }            

            }

            Console.WriteLine("Saralashdan keyin:");

           for (int i = 0; i < mas.Length; i++)

           {

           Console.WriteLine (mas[i].ToString());

           }

            Console.ReadKey();

        }

    }


    }

2.3 1-rasm.



Dastur algoritmini ko’rib chiqamiz:





i=0

i++


Ha Yo’q




i++, j=i+1, j++

qop=mas[i]; mas[i]=mas[j]; mas[j]=qop


Ha


i++


Ha


Yo’q




XULOSA


Men ushbu kurs ishini yozish davomida Algoritmlar nazaryasi fanini va dasturlash texnalogiyalarini ya’ni dasturchilikni o’rganishda algoritmlar nazaryasi fanini dasturlash tillariga bog’lashni, dasturlarning algoritmlarini tuzishni o’rganishga bo’lgan bilimlarni egallashda katta poydevor bo’ldi. Ushbu kurs ishi orqali bilim va ko’nikmalarimni oshirib oldim, men kelajakda ushbu bilimlarimni rivojlantirib yetuk mutaxasis bo’lishga harakat qilaman.

Saralash orqali ko’p masalalarni hal qilsa bo’ladi. Katta-katta masalalarni oddiy va sodda qilib ishlab chiqsa bo’lar ekan. Bu kurs ishi orqali saralashning qanchlik qiziqarli va samarali mavzu ekanligini bildim. Bundan tashqari juda ko’p yangi usullar orqali saralash bilan turli xil chiroyli va qiziqarli masalarni hal qilish, va shu kabi misollarni tez bajara olish qobilyatini hosil qildim. Bu kurs ishi orqali men mustaqil oddiy saralashlarni hal qiladigan dasturlar tuza olish qobilyatiga ega bo’ldim.

Kundalik hayotimizda juda ko’p qo’llaniladigan saralash har doim har bir ishimizda foydalanamiz. O’ylaymanki bu kurs ishi dasturlash olamiga kirib borishimga katta poydevor vazifasini o’tab beradi.

FOYDALANILGAN ADABIYOTLAR


1. Абрамов С.А. и др. Задачи по программированию.-М.:Наука, 1988.-224 стр.

2. Gulomov S.S. va boshqalar. Axborot tizimlari va texnologiyalari. Toshkent, 2000

3. Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. - М: Мир, 1979 г., 535 с.

4. Вирт Н.. Алгоритмы и структуры данных. – Досса, Хамарайан, 1997.

5. Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы.-М: Мир, 2000 г. 6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.- 960 с.

7. Лебедев В.И. Введение в системы программирования. М: Статистика, 1975

8. Поляков Д.Б., Круглов И.Ю. Программирование в среде Turbo Pascal: Справ.-метод. пособие.- М.: Изд-во МАИ, 1992.-576 с.

9. Попов В.В. Общение с ЭВМ на естественном языке. М:Наука, 1982.

10.Тыугу Х. Концептуальное программирование. М: Наука, 1984.

11.Успенский В.А., Семенов А.Л.. Теория алгоритмов: основные открытия и приложения. М: Наука, 1987, 287 с.

12.Файсман А. Профессиональное программирование на Турбо-Паскале.- Info&F, 1992.-270 стр.

INTERNET SAYTLAR.

1. http:\\acm.tuit.uz

2. http:\\Referat.arxiv.uz

3. http:\\Ziyonet.uz

4. http:\\dastur.uz

5. http://fayllar.org




Download 1.2 Mb.

Do'stlaringiz bilan baham:
1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling