Rivojlantirish vazirligi muhammad al-xorazmiy nomidagi

O'ZBЕKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI

RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKЕNT AXBOROT TЕXNOLOGIYALARI

UNIVЕRSITЕTI

“Axborot texnologiyalari” kafedrasi

Laboratoriya ishi bo`yicha

HISOBOT

Bajardi: Sobirjonov O’tkirbek 415-19

Tekshirdi: Bo’riyev Yusufjon


TOSHKENT 2020

Labarotoriya ishi 3

Saralash usul va algoritmlarini tadqiq qilish. Saralashga doir misollarni hal qilish.

Pufaksimon saralash algoritmi

Ushbu usulning g„oyasi quyidagicha: 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 (1- rasm).

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

1-rasm. Pufaksimon saralash usulida massivelementlarining o„rnini almashtirish

Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan pastga o„tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin.

Taqqoslashlar soni:

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

Almashtirishlar soni:

C_max=3n²/4

2-rasm. Massivni pufaksimon saralashga misol

2-rasmda berilgan misolda 5 ta elementdan iborat massiv berilgan. Demak, massivda pastdan yuqoriga (yuqoridan pastga) o„tishlar soni 5-1=4 marta bo„ladi. Misoldan ko„rinib turibdiki, algoritm ichki siklda 3-qadamdan boshlab massivni “bekor” qayta ishlaydi, 4-qadamni bajarmasa ham bo„ladi.

Berilgan usullarning afzalligi:

1) Eng sodda algoritm;

2) Amalga oshirish sodda;

3) Qo„shimcha o„zgaruvchilar shart emas.

Kamchiliklari:

1) Katta massivlarni uzoq qayta ishlaydi;

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] < a[j - 1]){

int x= a[j - 1];

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

a[j] = x; }

O’rinlashtirish va taqqoslashlar soni: (n* log( n )).

Dastur Sharti:

A massiv elementlari qiymatlarini kamayish tartibida saralash dasturini tuzing.

Dastur Codi:

// 22variant.cpp : Defines the entry point for the console application.

//22.A massiv elementlari qiymatlarini kamayish tartibida saralash dasturini tuzing.

//Sobirjonov O'tkirbek

#include "stdafx.h"

#include

using namespace std;

int main(){

int massiv[50];

int n;

cout<<"Elementlar soni : "; cin>>n;

for(int i=0; i

cout<<"Array["<

cin>>massiv[i];

}

int maxnumber = n;

// ------------------ Buble Sort -----------------

for(int i=0; i

for(int j=0; j

if(massiv[j]

int key = massiv[j+1];

massiv[j+1]=massiv[j];

massiv[j] = key;

}

}

maxnumber--;

}

//-------------------- Output --------------------

for(int i=0; i

cout<

}

system("pause");

return 0;

}
Dastur Natijasi:

Sof Natija: