Nazariy qism(1-90) Massivlarni saralash algoritmlari

NAZARIY QISM(1-90)

1. 
   Massivlarni saralash algoritmlari.
   

(boshi,2 va 3 savollarda)

Taroqsimon saralash

Pufaksimon saralashning yana bir modifikatsiyasi. "Toshbaqalar" dan qutulish uchun biz elementlarni masofadan turib qayta joylashtiramiz. Keling, uni tuzatamiz va agar kerak bo'lsa, ularni qayta tartibga solib, elementlarni shu masofada taqqoslab, chapdan o'ngga boraylik. Shubhasiz, bu "toshbaqalar" ga massivning boshiga tezda etib borishiga imkon beradi. Dastlab massivning uzunligiga teng masofani bosib, keyin uni taxminan 1,247 ga teng bo'lgan bir necha omillarga bo'lish maqsadga muvofiqdir. Masofa birga teng bo'lganda, pufaksimon saralash amalga oshiriladi.

2. 
   
   

#include

#include

//@TBCLbot

using namespace std;

int main()

{

int k;

cout<<"k="; cin>>k;

int A[k];

int k1=k;

srand(time(NULL));

{

b = false;

for(int i=0; i+1

{

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

{

swap(A[i],A[i+1]);

b = true;

}

}

}

for(int i=0; i

{

A[i]=rand()%100;

cout<

}

cout<
double l = 1.243309;

int step = k-1;

while (step>1)

{

for (int i = 0; i+step < k; i++)

{

if (A[i] > A[i + step])

{

swap(A[i], A[i + step]);

}

}

step /=l;

}

bool b =true;

while(b)

for(int i=0; i

{

cout<

}

}

Joylashtirish usuli bo’yicha saralash

Algoritm tugagandan so'ng javobni o'z ichiga oladigan massiv yarataylik. Javoblar massividagi elementlar har doim saralanishi uchun biz navbatma-navbat asl massivdan elementlarni kiritamiz

3. 
   
   
4. 
   
   
5. 
   #include
   
6. 
   #include
   
7. 
   
   
8. 
   using namespace std;
   
9. 
   int main()
   
10. 
    {
    
11. 
    int k;
    
12. 
    cout<<"k="; cin>>k;
    
13. 
    int A[k];
    
14. 
    int k1=k;
    
15. 
    srand(time(NULL));
    
16. 
    for(int i=0; i
17. 
    {
    
18. 
    A[i]=rand()%100;
    
19. 
    cout<
20. 
    }
    
21. 
    cout<
22. 
    
    
23. 
    
    
24. 
    for(int i=1; i
25. 
    {
    
26. 
    int j=i;
    
27. 
    while(j>0 && A[j-1]>A[j]){
    
28. 
    swap(A[j-1],A[j]);
    
29. 
    j--;
    
30. 
    }
    
31. 
    }
    
32. 
    for(int i=0; i
33. 
    {
    
34. 
    cout<
35. 
    }
    
36. 
    }
    
37. 
    
    

2. Massivlarni tanlash usuli bo’yicha saralash. 1. Tanlash usuli (Selected sort) bo’yicha saralash

Tanlash usuli saralash algoritmi massivni saralanmagan qismdan (o'sish tartibini hisobga olgan holda) minimal elementni bir necha bor topib, boshiga qo'yish orqali qatorni saralaydi. Algoritm berilgan massivda ikkita kichik jadvalni saqlaydi.

1) allaqachon tartiblangan ichki massiv.

2) saralanmagan qolgan ichki massiv.

Tanlash tartibining har bir takrorlanishida tartiblanmagan pastki qatordan minimal element (o'sish tartibini hisobga olgan holda) tanlanadi va saralangan pastki qatorga ko'chiriladi.

Quyidagi misol yuqoridagi qadamlarni tushuntiradi:

#include

using namespace std;

//@TBCLbot

void selectionSort(int arr[], int n)

{

int i, j, min_idx;

for (i = 0; i < n-1; i++)

{

min_idx = i;

for (j = i+1; j < n; j++)

if (arr[j] < arr[min_idx])

min_idx = j;

swap(arr[min_idx], arr[i]);

}

}

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

cout << arr[i] << " ";

cout << endl;

}

int main()

{

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr)/sizeof(arr[0]);

selectionSort(arr, n);

cout << "Saralangan massiv: \n";

printArray(arr, n);

return 0;

}