Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazimiy nomidagi toshkent axborot texnologiyalari universiteti

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI

VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZIMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Algoretmlarni loyihalash fani : bo‘yicha


1-Labaratorya ishi




Mavzu: . Ma’lumotlarni saralash algoritmlarini tartibli statistikasi.


Guruh:CAL009-L3 talabasi

Topshirdi: Odinayev Ilhom

Toshkent-2020

Laboratoriya ishi №1. Ma’lumotlarni saralash algoritmlarini tartibli statistikasi.

Ishdan maqsad: Talabalarda algoritmlarni asimptotik tahlil qilish haqida ko’nikmalar hosil qilish, masalalarni yechishda saralash, qidirish algoritmlarini qo’llash va ularni tahlil qilish orqali qulayini tanlash.

Birinchi topshiriq bo’yicha variantlar

Ro’yhat bo’yicha variant nomeri	Massivni to’ldirish	Saralash metodi	Har bir metod uchun massivdagi elementlarning soni
10,11,12	Tasodifiy elementlar bilan to’ldirilgan massiv	Surish Sheyker Tezkor	500	1600	5000

№:12

#include

using namespace std;

//show function

void show( int x[], int n){

for (int i=0; i

cout<

}

cout<

}

//random number

void print( int x[], int n){

srand(time(0));

for (int i=0; i

x[i]=(rand()%200);

}

}

//Shaker sort

void shakerSort(int a[], int n)

{

bool swapped = true;

int comparisons = 0;

int swaps = 0;

int start = 0;

int end = n;

while (swapped==true)

{

swapped = false;

for (int i = start; i < end-1; ++i)

{

comparisons++; //count comparisons

if (a[i] > a[i + 1])

{

int temp = a[i];

a[i] = a[i+1];

a[i+1] = temp;

swapped = true;

swaps++; //count swaps

}

}

if (swapped==false)

{

break;

}

swapped = false;

end = end-1;

for (int i = end-1; i >=start; i--)

{

comparisons++; //count comparisons

if (a[i] > a[i+1])

{

int temp = a[i];

a[i] = a[i+1];

a[i+1] = temp;

swapped = true;

swaps++; //count swaps

}

}

start = start+1;

}

cout<<"Shaker Sort "<

}

//Quick sort

int swaps=0;

int quickSort(int arr[], int left, int right) {

if (right <= left)

return 0;

int mid = (right + left - 1)/2;

int pivot = arr[mid];

arr[mid] = arr[left];

arr[left] = pivot;

int split = left + 1, tmp;

for (int track = left + 1; track < right; track++) {

if (arr[track] < pivot) {

tmp = arr[track];

arr[track] = arr[split];

arr[split] = tmp;

split++;

swaps++;

}

}

tmp = arr[split - 1];

arr[split - 1] = arr[left];

arr[left] = tmp;

int split1 = split - 1;

int count = right - left - 1;

count += quickSort(arr,left,split1);

count += quickSort(arr,split1 + 1,right);

return count;

}

//Insertion sort

int insertsort(int a[], int n){

int no_swap = 0, comp = 0;

for (int i = 1; i < n; i++) {

int j = i;

comp++;

while ((j > 0) && (a[j - 1] > a[j])) {

if(a[j-1]>a[j]){

comp++;

}

int temp = a[j - 1];

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

a[j] = temp;

j--;

no_swap++;

}

}

cout<<"Inserion sort " <

}

int main()

{ int n=500, m=1600, p=5000;

int a[n],b[m], c[p];

cout<<"-------Birinchi a[500] massiv berilishi:------- \n\n";

print(a,n);

show(a,n);

cout<<"\n--------Ikkinchi b[1600] massiv berilishi:--------- \n\n";

print(b,m);

show(b,m);

cout<<"\n-----------Uchinchi c[5000] massiv berilishi:--------- \n\n";

print(c,p);

show(c,p);

cout<<"\n\n";

cout<<"\n__________________________________________________________________\n";

cout<

cout<<"\nSaralash nomi: | nmb of comparisons | nmb of swaps\n";

int q=quickSort(a, 0 ,n);

cout<<"Quick Sort "<

print(a,n);

shakerSort(a,n);

print(a,n);

insertsort(a,n);

cout<<"\n__________________________________________________________________\n";

cout<

cout<<"\nSaralash nomi: | nmb of comparisons | nmb of swaps\n";

int h=quickSort(b, 0 ,m);

cout<<"Quick Sort "<

print(b,m);

shakerSort(b,m);

print(b,m);

insertsort(b,m);

cout<<"\n__________________________________________________________________\n";

cout<

cout<<"\nSaralash nomi: | nmb of comparisons | nmb of swaps\n";

int l=quickSort(c, 0 ,p);

cout<<"Quick Sort "<

print(c,p);

shakerSort(c,p);

print(c,p);

insertsort(c,p);

return 0;

}



2 – topshiriq

C++ (Python, Java) tilida quyida keltirilgan amallarni bajargan holda ustuvor navbat tashkil qiling:

• 
  Berilgan N ta elementdan iborat ustuvor navbat hosil qiling;
  
• 
  Yangi element qo’shing;
  
• 
  Eng katta elementni yechib oling;
  
• 
  Berilgan qandaydir elementni yechib oling;
  
• 
  Ikkita ustuvor navbatni birlashtiring.
  

#include

#include

using namespace std;

void showpq(priority_queue gq)

{

priority_queue g = gq;

while (!g.empty())

{

cout<< g.top()<<' ';

g.pop();

}

cout << '\n';

}

int main()

{

priority_queue pqueue;

priority_queue pqueue2;

pqueue2.push(3);

pqueue2.push(5);

pqueue2.push(1);

pqueue2.push(7);

pqueue2.push(9);

pqueue2.push(3);

pqueue2.push(2);

int n;

cout<<"navbat elementlari soni kiriting: ";

cin>>n;

int a[n];

for (int i=0; i

cin>>a[i];

pqueue.push(a[i]);

}

cout<<"\nNavbatning berilishi: \n";

showpq(pqueue);

mark:

cout<<"\n\n____________MENYU____________ \n";

cout<<"1. Yangi element qo'shish \n";

cout<<"2. Eng katta elementni yechib olish \n";

cout<<"3. Berilgan qandaydir elementni yechib olish \n";

cout<<"4. Ikkita ustuvor navbatni birlashtiring \n";

int x;

cin>>x;

cout<

switch(x){

case 1:{

int b;

cout<<"biror bir son kiriting: ";

cin>>b;

pqueue.push(b);

showpq(pqueue);

break;

}

case 2:{

cout<<"Navbatdagi eng katta element: "<


pqueue.pop();

cout<<"Eng katta element yechib olingandan keyin: \n";

showpq(pqueue);

break;

}

case 3:{

pqueue.pop();

showpq(pqueue);

break;

}

case 4:{

cout<<"berilgan ikkinchi priority queue elementlari: \n";

showpq(pqueue2);

while (!pqueue2.empty())

{

pqueue.push(pqueue2.top());

pqueue2.pop();

}

cout<<"\nIkkita navbatning qo'shilgani: \n";

showpq(pqueue);

break;

}

default: cout<<"Mavjud bo'lmagan buyruqni tanladingiz";

}

cout<<"\nBosh menyuga qaytasizmi? (ha/yo'q)\n";

string s;

cin>>s;

if(s=="ha"){

goto mark;

}else{

exit;

}

}