Mavzu: Piramidali saralash algoritmlari Mundarija

Misol:
#include
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for (int i = 0; i < n; i++)
cin>>a[i];
for (int i = n-1; i >= 1; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j+1]) {
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
for (int i = 0; i < n; i++)
cout<
return 0;
}

• 
  Ishlash vatqi ( ).
  
• 
  Taqqoshlashlar soni ( ).
  
• 
  Almashtirishlar soni ( ).
  
• 
  Qo’shimcha xotira .
  

1.4.Birlashtirish orqali saralash(Merge Sort) algoritmi.

Bu algoritm Jon fon Neyman tamonidan 1946 yilda taklif qilingan.Jon Fon Neyman Vengriyalik matematika, kvant fizikasi, funksional analiz, to’plamlar nazariyasi, ekonomika, informatika kabi fanlarga munosib hissa qo’shgan.
Algoritmi:


















[L, R] oraliq m=(L+R) / 2 o’rtasi orqali ikkita [L, m] va [m+1, R] oraliqqa ajratiladi va ular alohida saralanadi.

Misol:
#include
#include
#include
using namespace std;
int a[100000], b[100000];
void mergesort(int L, int R) {
if (L >= R)
return;
else {
int m = (L+R) / 2;
mergesort(L, m);
mergesort(m+1, R);
//Birlashtirish yoziladi
}
}
int main() {
int n;
cin>>n;
for (int i = 0; i < n; i++)
cin>>a[i];
mergesort(0, n-1);
for (int i = 0; i < n; i++)
cout<
return 0;
}

1.5.Tezkor saralash(Quick Sort) algoritmi.

1964 yilda Charlz Hoar tamonidan taklif qilingan.
Charlz Hoar ingliz olimi, informatika va hisoblash texnikasi sohasida yetuk mutaxassis. Uning “Tezkor saralash” algoritmi saralash bo’yicha eng ommobop algoritm. Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi.
Algoritmning g’oyasi:
Massivda bo’luvchi element X tanlanadi.
Elementlarni shunday joylashtiramizki, dastlab X dan kichik yoki teng bo’lgan elementlar joylashsin, keyin undan katta bo’lgan elementlar joylashsin.
Keyin ularni alohida saralaymiz.

• 
  [L, R] saralanishi kerak bo’lgan oraliq.
  
• 
  m = (L+R) / 2 – kesmanig o’rtasi.
  
• 
  X=a[m] - bo’luvchi element.
  

• 
  Chap tamondan X dan kichik katta yoki teng bo’lgan birinchi elementni topamiz.
  
• 
  O’ng tamondan X dan katta bo’lmagan birinchi elementni topamiz.
  
• 
  Ikkalasining qiymatini almashtirzmiz.
  

Misol:
#include
using namespace std;
int a[100001];
void qsort(int L, int R) {
int m = (L+R) / 2;
int X = a[m];
int i = L;
int j = R;
while (i <= j) {
while (a[i] < X) i++;
while (a[j] > X) j--;
if (i <= j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
i++;
j--;
}
}