Tizimlivaamaliydasturlashtirishkafedrasi

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Tizimlivaamaliydasturlashtirishkafedrasi

Ma’lumotlartuzilmasivaalgoritmifanidan

Mustaqil ishi

Guruh: 029

Bajardi: Raximjanov Davronbek

Tekshirdi :Akbarova Marg’uba

TOSHKENT 2019

REJA:

I . Kirish.

2. 
   Asosiy qism:
   

1. Saralash tushunchasi va vazifasi.

2. Saralash usullarining klassifikatsiyasi.

3. Saralash algoritmlarining samaradorligini ko’rish uchun misollar .

2. 
   Xulosa.
   

Kirish

Saralash deb, berilgan obyektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktab jismoniy tarbiya darsi. Bu dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida esa sinf jurnalidagi familyalar ketma-ketligiga qarab topshirishadi. Shu yerning o`zida 2ta saralashdan foydalanilyapti. Biri, bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalidagi o`rinlar bo`yicha.

Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma-bir tahlil qilib chiqamiz(buning uchun saralanmagan sonlar ketma-ketligini olamiz):

Sonlar berilishi: 23, 54, 3, 22, 1, 45;

1. 
   Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o`z o`rnida turibdi)
   
2. 
   Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son)
   
3. 
   Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi)
   
4. 
   Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi)
   

Demak, miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma`lumki, bizning miyamiz o`zi optimal deb bilgan yo`nalishdan ketadi va biz uchun faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo`lmaydi. Dasturlashga talab ortib, bu soha rivojlanib borgani sari unda bir qator sohalardagi kabi tezlikni oshirish muammosi paydo bo`ladi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o`rinda savol tug`iladi, operatsion tizimlarda ham saralashdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil saralash mavjud: fayl turi, nomi, o`zgartirilgan sanasi va o`lchami. Har birini o`sish yoki kamayish tartibida saralash mumkin. Ha aytgancha, hozirgi tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki tezlik masalasi tobora yuqori cho`qqiga chiqayotgan va ishlanayotgan ma`lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish kulguli. Ma`lumotlar o`lchamlari esa juda katta, shu sabali ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga oshirish uchun esa yangi algoritmlarga ehtiyoj tug`ila boshladi. Buni yechimi sifatida bir necha turdagi algoritmlardan foydalaniladi. Ular:

1. 
   Bubble sort;
   
2. 
   Selection sort;
   
3. 
   Insertion sort;
   
4. 
   Quick sort;
   
5. 
   Merge sort.
   

Bundan tashqari ko’plab saralash algoritmlari mavjud. Ushbu mustqil ish ichida shu va boshqa saralash algotirmlari bo’yicha bilib olamiz.

Asosiy qism
Ma’lumotlarnikompyuterdaqaytaishlashdaelementninginformatsionmaydonivauningmashinaxotirasidajoylashishinibilishzarur. Shu maqsaddama‟lumotlarnisaralashamalgaoshiriladi. Demak, saralash – buma‟lumotlarnikalitlaribo„yichadoimiyko„rinishdamashinaxotirasidajoylashtirishdaniborat. Buyerdadoimiylikma’lumotlarnimassivdakalitlaribo„yichao„sishitartibidaberilishitushuniladi.

Ma‟lumotlargaqaytaishlovberilayotgandama‟lumotninginformatsionmaydoninihamdauningmashinadajoylashishini (adresini) bilishzarur.

Saralashning ikkita turi mavjud: ichki va tashqi:

-ichkisaralash-operativxotiradagisaralash;

-tashqisaralash – tashqixotiradasaralash.

Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma‟nosida) talab qiladi. Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma‟lumot ko„rsatkichlari almashtirilib, massiv o„z joyida qoladi. Bu usul adreslar jadvalini saralash usuli deyiladi. Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir xil kalitlilar boshlang„ich tartibda qanday joylashgan bo„lsa, shu tartibda qoldirilishi maqsadga muvofiq bo„ladi (Bir xil kalitlilar o„zlariga nisbatan). Bunday usulga turg„un saralash deyiladi.

Saralash samaradorligini bir necha mezonlar bo„yicha baholash mumkin:

 saralashga ketgan vaqt;

 saralash uchun talab qilingan operativ xotira;

 dasturni ishlab chiqishga ketgan vaqt.

Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki almashtirishlar sonini hisoblash mumkin.

Faraz qilaylik, N = 0,01n2 + 10n – taqqoslashlar soni. Agar n < 1000 bo„lsa, u holda ikkinchi qo„shiluvchi katta, aks holda ya‟ni, n > 1000 bo„lsa, birinchi qo„shiluvchi katta bo„ladi.

Demak, kichkina n larda taqqoslashlar soni n ga teng bo„ladi, katta n larda esa n2 ga teng bo„ladi.

Saralashda taqqoslashlar soni quyidagi oraliqlarda bo„ladi:

dangacha; – ideal holatda.

Saralashningquyidagichausullaribor:

qat‟iy (to„g„ridan-to„g„ri) usullar;

yaxshilanganusullar.

Qat‟iyusullarningafzalliklariniko„ribchiqaylik:

1. Bilamizki, dasturlarningo„zlari ham xotirada joy egallaydi. To„g„ridan-to„g„risaralashusullariningdasturlariqisqabo„lib, ulartushunishgaoson.

2. To„g„ridan-to„g„risaralashusullariorqalisaralashtamoyillariningasosiyxususiyatlarinitushuntirishqulay.

3. Murakkablashtirilganusullardaunchako„pamallarnibajarishtalabqilinmasada, ushbuamallarningo„zlari ham anchamurakkabdir. Garchiyetarlichakatta n lardaulardanfoydalanishtavsiyaetilmasada, kichik n lardamazkurusullartezroqishlaydi.

Shu joynio„zidaqat‟iyusullarniishlashtamoyillarigako„ra 3 ta toifagabo„lishmumkin:

1. To„g„ridan-to„g„riqo„shishusuli (by insertion);

2. To„g„ridan-to„g„ritanlashusuli (by selection);

3. To„g„ridan-to„g„rialmashtirishusuli (by exchange).

To„g„ridan-to„g„riqo„shishusulibilansaralashalgoritmi

Bundayusulkartao„yinidakengqo„llaniladi. Elementlar (kartalar) hayolan “tayyor” a(1),...,a(i-1) vaboshlang„ichketma-ketliklargabo„linadi. Harbirqadamda (i=2 danboshlanib, harbirqadamdabirbirlikkaoshiribboriladi) boshlang„ichketma-ketlikdani-chi element ajratibolinibtayyorketma-ketlikningkeraklijoyigaqo„yiladi.

To„g„ridan-to„g„riqo„shishorqalisaralashalgoritmiquyidagichabo„ladi:

for (int i=1;i

x=a[i];

x nia[0]...a[i] oraliqningmosjoyigaqo‘shish

}

Keraklijoyniqidirishjarayoniniquyidagitartibdaolibborishqulaybo„ladi. 2-elementdan boshlabharbirelementniqarabchiqamiz, ya‟niharbir element o„zidanoldinturgan element bilansolishtiriladi. Agar qaralayotgan element kichikbo„lsa, oldindaturgan element bilano„rinalmashadivayanao„zidanoldindaturgan element bilansolishtiriladi, jarayonshukabidavometadi. Bu jarayonquyidagishartlarningbirortasibajarilgandato„xtatiladi:

1. x elementioldidauningkalitidankichikkalitlia(j) elementichiqqanda.

2. x elementioldida element qolmaganda.

for (int i=1;i

while(a[j]

int t=a[j-1];

a[j-1]=a[j];

a[j]=t;

j=j-1;

}

}


Algoritm samaradorligi
Farazqilaylik, taqqoslashlarsoniC, o„rinlashtirishlarsoniM bo„lsin. Agar massivelementlarikamayishtartibidabo„lsa, u holdataqqoslashlarsoniengkattabo„lib, u gatengbo„ladi, ya‟ni .O„rinlashtirishlarsoniesagatengbo„ladi, ya‟ni . Agar berilganmassivo„sishtartibidasaralanganbo„lsa, u holdataqqoslashlarvao„rinlashtirishlarsoniengkichikbo„ladi, ya‟ni , .

Tanlashorqalisaralashalgoritmi

Mazkurusulquyidagitamoyillargaasoslangan:

1. Eng kichik kalitga ega element tanlanadi.

2. Ushbu element birinchi element bilano„rinalmashinadi.

3. Keyinmazkurjarayonqolgann-1, n-2 elementlarbilantakrorlanib, to bittaeng “katta” element qolgunchadavomettiriladi.

for(int i=0;i

for(int j=i+1;j

if (a[i] > a[j]){

int k = a[j];

a[j]= a[i];

a[i]= k;

}

Algoritmsamaradorligi:

Taqqoslashlarsoni

S= N(N-1)/2=(N²-N)/2

Massivtartiblangandao„rinlashtirishlarsoni

M_min=3(N-1)

Massivteskaritartiblangandao„rinlashtirishlarsoni

M_min=M_minN/2=3N(N-1)/2

Ushbuusulbo„yichasaralashbajarilsa, engyomonholdataqqoslashlarvao„rinlashtirishlarsonitartibi n2 bo„ladi.

Pufaksimonsaralashalgoritmi

Ushbuusulningg„oyasiquyidagicha: n - 1 martamassivdaquyidanyuqorigaqarabyuribkalitlarjufti-juftibilantaqqoslanadi. Agar pastkikalitqiymatiyuqoridagijuftikalitidankichikbo„lsa, u holdaularningo„rnialmashtiriladi (1- rasm).

Misol :massiv - 4, 3, 7, 2, 1, 6.

1-rasm. Pufaksimonsaralashusulidamassivelementlariningo„rninialmashtirish

Pufaksimonusulnimassivelementlaridapastdanyuqorigavayuqoridanpastgao„tishnibirvaqtdaamalgaoshirishnatijasidayaxshilashmumkin.

Taqqoslashlarsoni:

M=(n/2)(n/2)=n²/4

Almashtirishlarsoni:

C_max=3n²/4

2-rasm. Massivnipufaksimonsaralashgamisol

2-rasmda berilganmisolda 5 ta elementdaniboratmassivberilgan. Demak, massivdapastdanyuqoriga (yuqoridanpastga) o„tishlarsoni 5-1=4 martabo„ladi. Misoldanko„rinibturibdiki, algoritmichkisiklda 3-qadamdan boshlabmassivni “bekor” qaytaishlaydi, 4-qadamni bajarmasa ham bo„ladi.

Berilganusullarningafzalligi:

1) Engsoddaalgoritm;

2) Amalga oshirishsodda;

3) Qo„shimchao„zgaruvchilarshartemas.

Kamchiliklari:

1) Kattamassivlarniuzoqqaytaishlaydi;

2) Har qanday holatda ham o„tishlar soni kamaymaydi.

“Pufaksimon” usulni yaxshilash

1) Agar massivda o„tishlar nafaqat yuqoridan pastga, balki bir vaqtning o„zida pastdan yuqoriga ham bo„lsa, u holda “yengil” elementlar “yuqoriga suzib” chiqadi va “og„ir” elementlar esa “cho„kadi”.

2) Massivda “bekor” o„tishni yo„q qilish uchun, tashqi siklda massiv saralanganligini tekshiruvchi belgi qo„yish lozim.

for (int i=0;i

for (int j=n-1;j>i;j--)

if (a[j]

int x= a[j - 1];

a[j - 1] = a[j];

a[j] = x; }

O’rinlashtirishvataqqoslashlarsoni: (n* log( n )).

Quiksort – tezsaralashalgoritmi

Bu algoritm “bo„libolvaegalikqil” tamoyiliningyaqqolmisolidir. Bu algotirmrekursivbo„lib, o„rtachaN*log2N ta solishtirishnatijasidasaralaydi. Algoritmberilganmassivnisaralashuchununi 2 tagabo„liboladi. Bo„libolishuchunixtiyoriyelementnitanlabundan 2 ta qismgaajratiladi. Lekin o„rtadagi elementni tanlab, massivning teng yarmidan 2 ga ajratgan ma‟qul. Tanlangan kalit elementga nisbatan chapdagi va o„ngdagi har bir element solishtiriladi. Kalit elementdan kichiklar chapga, kattalar o„ng tomonga o„tkaziladi (6.3-rasm). Endi massivning har ikkala tomonida xuddi yuqoridagi amallar takrorlanadi. Ya‟ni bu oraliqlarning o„rtasidagi elementlar kalit sifatida olinadi va h.k.

Misol uchun rasmdagi massivni saralash algoritmini ko„rib chiqamiz.

1. Oraliq sifatida 0 dan n-1 gacha bo„lgan massivning barcha elementlarini olamiz.

2. Oraliq o„rtasidagi kalit elementni tanlaymiz, ya‟ni

key=(+)/2, i=,

j=.

3-rasm. Quicksort algoritmidao„rinlashtirish

3. Chapdagii-elementnikey bilansolishtiramiz. Agar key kichikbo„lsa, keyingiqadamgao„tamiz. Aksholdai++ vashuqadamnitakrorlaymiz.

4. O„ngdagij-element bilankey solishtiriladi. Agar key kattabo„lsa, keyingiqadamgao„tamiz, aksholdaj-- vashuqadamnitakrorlaymiz.

5. i- vaj-elementlarningo„rnialmashtiriladi. Agar i<=j bo„lsa, 3-qadamga o„tiladi.
Birinchio„tishdankeyintanlangan element o„ziningjoyigakelibjoylashadi.

6. Endishuko„rilayotganoraliqdakey kalitning chap tomonidaelementlarmavjudbo„lsa, ularustidayuqoridagiamallarnibajarishlozim, ya‟niko„riladiganoraliq0 dankey-1 gacha deb belgilanadiva 2-qadamga o„tiladi. Aksholdakeyingiqadamgao„tiladi.

7. Endishuko„rilayotganoraliqdakey kalitningo„ngtomonidaelementlarmavjudbo„lsa, ularustidayuqoridagiamallarnibajarishlozim, ya‟niko„riladiganoraliqkey+1 dann-1 gacha deb belgilanadiva 2-qadamga o„tiladi. Aksholdaalgoritmtugaydi.
Shu algoritmgamisolko„ribchiqamiz.

Misol: Talabalar ism-sharifivatartibraqamidaniboratjadvalni quicksort algoritmibilansaralangvanechtao„rinlashtirishamalgaoshirilganinianiqlang.

Dasturkodi

#include

#include

using namespace std;

structtable{

int t;

string FIO;};

int q=0;

void qs(table *a,intfirst,int last){

inti = first, j = last;table x =a[(first + last) / 2];

do {

while (a[i].FIO

while (a[j].FIO>x.FIO) j--;

if(i <= j) {

if (i

i++;

j--;

}

} while (i <= j);

if (i < last)

qs(a,i,last);

if (first < j)

qs(a,first,j);

}

intmain(intargs, char *argv[])

{ intn;cout<<"n=";cin>>n;

table talaba[n];

for(inti=0;i

talaba[i].t=i+1;

cin>>talaba[i].FIO;

}

qs(talaba,0,n-1);

for(int i=0;i

cout<

cout<<"quicksort algoritmi "<

}

Dastur natijasi:

talabalar sonini kiriting=5

5 ta talabalar FIO sini kiriting

Farhod

Asror

Sobir

Bobur

Vali

| 2 | Asror |

| 4 | Bobur |

| 1 | Farhod |

| 3 | Sobir |

| 5 | Vali |

Java dasturlash tilidagi saralashdan foydalanilgan real proekt (Davronbek Raximjanov):

<<>> N ta talabadan iborat guruh tuzilsin. Quyidagi ma’lumotlar berilgan: FISH, yoshi, Ta’lim yo’nalishi, fanlar boyicha baxosi:MTA, oily matematika va boshqa fanlardan .
Shunda talabalarning ball bo’yicha o’sish tartibida saralansin.

Kodi:

package com.company;
import java.util.Scanner;
public class Main {

public static void main(String[] args) {

Talaba talaba0 = new Talaba("Rasulov Hamid ", "KIF", 50);
Talaba talaba1 = new Talaba("Homidov Asror", "KIF", 45);
Talaba talaba2 = new Talaba("Tulaganov Xayitbek", "Kutubxonachilik", 56);
Talaba talaba3 = new Talaba("Humoyunov Jumavoy", "Kasb Ta'limi", 70);
Talaba talaba4 = new Talaba("Abdusattorova Karima", "DIF", 90);

Talaba Talabalar[] = new Talaba[5];

Talabalar[0] = talaba0;
Talabalar[1] = talaba1;
Talabalar[2] = talaba2;
Talabalar[3] = talaba3;
Talabalar[4] = talaba4;

System.out.println("oldingi holat: " );

System.out.println();
System.out.println();

for (int i = 0; i
System.out.println(Talabalar[i]);

}
Talaba talabaY;

for (int i = 0; i for (int j = 1; j < Talabalar.length; j++) {
if (Talabalar[j - 1].ball > Talabalar[j].ball) {
talabaY = Talabalar[j];
Talabalar[j] = Talabalar[j-1];
Talabalar[j-1] = talabaY;

}
}
}

int kiritish;

Scanner scanner = new Scanner(System.in);

kiritish = scanner.nextInt();

System.out.println();

System.out.println("Saralangan xolatda: " );
System.out.println();
System.out.println();

for (int i = 0; i
System.out.println(Talabalar[i]);

}}}

package com.company;

public class Talaba {

String FISh;
String fakultet;
int ball;

public Talaba(String FISh, String fakultet, int ball) {

this.FISh = FISh;
this.fakultet = fakultet;
this.ball = ball;
}

@Override

public String toString() {
return "Talaba{" +
"FISh='" + FISh + '\'' +
", fakultet='" + fakultet + '\'' +
", ball=" + ball +
'}';
}
}

Natijasi:

Xulosa

Xulosa qilib, saralash algoritmlarining samaradorligi va qiyosiy taxlili to’g’risida shuni aytishimiz mumkinki, turli xil ish jarayonlari uchun o’ziga mos va bog’liq bo’lgan saralash algoritmlari va mashina tiliga o’girish jarayonlarining qulay usullari ko’zdan kechiriladi. Ushbu usullar aynan o’zining natijasini namoyon etishda eng qulay va shunga bog’liq eng tezkor ekanligi aniqlangandan so’ng qo’llaniladi va shunga mos saralangan xolatdagi ro’yxatlar, o’bektlar va boshqa tuzilmalar natijasi o’laroq yuzaga chiquvchi yangi ro’yxat korinishidagi jadvallar namoyon bo’ladi. Biz esa shunday usullar tarkibiga kiruvchi saralash usullarining bir necha o’ziga xos turlari bilan tanishib chiqdik. Bular : Tanlashorqalisaralashalgoritmi, Pufaksimonsaralashalgoritmi , Quiksort – tezsaralashalgoritmi, va boshqalardir.


Foydalanilgan Adabiyotlar ro’yxati.

1. Алфред В. Ахо., Джон Э. Хопкрофт, Джефри Д. Ульман. Alfred V.Axo., Jon E.Xonkroft, Jefri D. Ulman.

Структура данных и алгоритмы//Учеб.пос., М. : Изд.дом: "Вильямс", 2000, -

384 с.

2.Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных в Delphi//СПб: ООО «ДиаСофтЮП», 2003. 560с.

3.Роберт Седжвик. Фундаментальные алгоритмы на C++. Анализ,

Структуры данных, Сортировка, Поиск//К.: Изд. «ДиаСофт», 2001.- 688 с.

4. Динман М.И. С++. Освой на примерах//СПБ.:БХВ-Петербург, 2006,

384.

5. Шилдт, Герберт. Полный справочник по С#//М. : Изд. дом

"Вильямc", 2004, 752 с.