2-laboratoriya mashg‘ulot Ma'lumot qidirish va saralash algoritmlari Nazorat savollari

2-laboratoriya mashg‘ulot

Ma'lumot qidirish va saralash algoritmlari

Nazorat savollari

1. 
   Qanday saralash algoritmlarini bilasiz?
   
2. 
   Saralash algoritmlari samaradorligini qanday baholash mumkin?
   
3. 
   Pufaksimon saralash algoritmi va uni yahshilangan usulini tushuntiring.
   
4. 
   To‘g‘ridan-to‘g‘ri qo‘shish, tanlash algoritmlarini farqini tushuntiring.
   
5. 
   Shella saralash algoritmini tushuntiring.
   
6. 
   Quicksort algoritmini tushuntiring.
   

Javoblar

1. To‘g‘ridan-to‘g‘ri qo‘shish usuli bilan saralash algoritmi, Tanlash orqali saralash algoritmi, Pufaksimon saralash algoritmi.

2. 
   Saralash algoritmlarini samaradorligi yuqori. Chunki juda ko’p malumot mavjud joydan o’zimizga kerakli malumotni topish qulay bo’ladi va ancha osonlashadi.
   
3. 
   Pufaksimon saralash algoritmi: n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo‘lsa, u holda ularning o‘rni almashtiriladi.
   

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”.

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

4. 
   To‘g‘ridan-to‘g‘ri qo‘shish:
   

Bunday usul karta o‘yinida keng qo‘llaniladi. Elementlar (kartalar) hayolan “tayyor” a(1),...,a(i-1) va boshlang‘ich ketma-ketliklarga bo‘linadi. Har bir qadamda (i=2 dan boshlanib, har bir qadamda bir birlikka oshirib boriladi) boshlang‘ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo‘yiladi.

Tanlash algoritmlarini:

Mazkur usul quyidagi tamoyillarga asoslangan:

1. Eng kichik kalitga ega element tanlanadi.

2. Ushbu element birinchi element bilan o‘rin almashinadi.

3. Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to bitta eng “katta” element qolguncha davom ettiriladi.

5.

6. Tez saralash(quicksort) algoritmi - Charlz Xoar tomonidan yaratilgan mashxur saralash algoritmidir. Ushbu algoritm n ta elementdan iborat massivni eng uzogʻi bilan O(n²) vaqtda saralaydi. Biroq algoritm bajarilish tezligining matematik kutilmasi O(n log n) ga teng va u boshqa shunday tezlikda bajariluvchi algoritmlardan tezroq ishlaydi.

5."Mersedes" markali mashina egalarini alifbo bo‘yicha teskari tartibda joylashtiring.

Algoritm

1. 
   Jadvalga mashina egalarini 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.
   
4. 
   Agar i bo‘lsa, i++ va 3-qadamga o‘tamiz.
   
5. 
   Natijaviy saralangan massivni ekranga chiqaramiz.
   

Dastur kodi

#include

#include

#include

using namespace std;

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

{

int n; cout<<"Mersedes mashina egalari sonini kiriting=";cin>>n;

struct table{

int t;

char FIO[40];

}

egalari[n];

cout<

for(int i=0;i

egalari[i].t=i+1;

cin>>egalari[i].FIO;

}

for(int i=0;i

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

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

table k=egalari[j-1];

egalari[j-1]=egalari[j];

egalari[j]=k;

}

}

}

for(int d=0;d<=n;d++)

cout<

system("PAUSE");

}