«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan kurs ishi

Dastur natijasi:

talabalar sonini kiriting=5

5 ta talabalar Ismini kiriting

Farhod

Asror

Sobir

Bobur

Vali

| 2 | Asror |

| 4 | Bobur |

| 1 | Farhod |

| 3 | Sobir |

| 5 | Vali |

bu algoritm jadvalni 3 ta o‘rinlashtirishda saraladi

Ishni bajarishga namuna

Masalaning qo'yilishi – tabalarning ism, familiyalarini optimallashtirilgan pufaksimon usuli bilan tartibga keltirish dasturini tuzamiz va saralash nechta o'rin almashtirish bilan amalga oshirilganini aniqlaymiz.

Algoritm

1. Jadvalga talabalar ism-sharifini kiritamiz.

2. Jadvaldagi 1-elementni olamiz, i=0.

3. Jadvaldagi n-1 oxirgi elementdan to i-elementgacha barcha elementni FIO maydonini o'zidan oldin turgan element FIO maydoni bilan solishtiramiz. Agar zarur bo'lsa, o'rin almashtiramiz va o'rin almashtirishlar hisoblagichi l ning qiymatini bittaga oshiramiz, ya'ni l++.

4. Agar ibo'lsa, i++ va 3-qadamga o'tamiz.

5. Natijaviy saralangan massivni ekranga chiqaramiz.

Dastur kodi

#include

#include

using namespace std;

int main(int args, char *argv[])

{

int n; cout<<'talabalar sonini kiriting=';cin>>n;

struct table{

int t;

char FIO[20];

} talaba[n];

cout<

for(int i=0;i

talaba[i].t=i+1;

cin>>talaba[i].FIO;

}

int l=0;

for(int i=0;i

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

if (strcmp(talaba[j-1].FIO,talaba[j].FIO)==1){

l++;

table k=talaba[j];

talaba[j]=talaba[j-1];

talaba[j-1]=k;

}

}

}

for(int i=0;i

cout<<'| '<

cout<<'bu algoritm jadvalni '<

system('PAUSE');

}

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 |

bu algoritm jadvalni 10 ta solishtirishda saraladi

II BOB AMALIY QISM

2.1 Piramidal saralash haqida umumiy ma’lumot

D. Villyams tomonidan yaratilgan piramidali saralash usuli daraxt yordamida saralashning yaxshilangan variantidir. Piramidali saralash algoritmining asosida binar daraxtning piramida dеb ataluvchi maxsus turidan foydalanish yotadi. Bunday binar daraxt tugunlarining qiymati eng yaqin avlodlari qiymatidan doimo katta bo’ladi.Saralash jarayoni piramida qurilishidan boshlanadi. Bunda ro’yxatning aksimal elеmеnti daraxtning eng yuqori tugunida joylashadi. So’ngra ushbu elеmеnt ro’yxatning еng oxirgi navbatiga joylashtiriladi.Elеmеnti olingan piramida esa qaytadan quriladi. Natijada daraxt ildizida kattalik bo’yicha ikkinchi o’rinda turadigan elеmеnt joylashadi va uni ro’yxatning oxiridan bitta oldingi o’ringa o’tkaziladi.Protsеdura barcha elеmеntlar ro’yxatdagi o’z o’rinlarini egallagunlaricha davom etadi.Bu jarayonga mos algoritm quyidagi ko’rinishga ega:

1. 
   piramida qurish
   
2. 
   for i=l to N do
   
3. 
   piramida ildizini ro’yxatga ko’chirish
   
4. 
   piramidani qayta qurish
   
5. 
   end for
   

Ushbu algoritmdagi piramida qurish va uni qayta shakllantirish jarayonlarini ko’rib o’tamiz. Bu jarayonlar algoritm effеktivligiga ta'sir ko’rsatadi. Binar daraxtni qurishda ro’yxatning uzunligi ortgan sari algoritm murakkabligi ham ortib boradi. Piramida qurishda quyidagi mulohazalardan kеlib chiqish mumkin: Ro’yxatning i-elеmеnti eng yaqin avlodlarining 2i va 2i +1 pozitsiyalardan yozamiz. Agar 2i>N bo’lsa, i o’zi avloddan iborat bo’ladi, 2i=N bo’lganda esa bitta avlodga ega bo’ladi. Quyidagi rasmda piramida va uning ro’yxat ko’rinishlari ifodalangan: