Reja: Saralash haqida tushuncha va algoritmlari

[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;'>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;

}

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

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

10

5

9

3

7

6

1

12

3

17

2

L



R

m

• 
  [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.
  
• 
  
  5
  
  9
  
  10
  
  7
  
  6
  
  1
  
  12
  
  10
  
  17
  
  2
  
  i
  
  j
  
  3
  
  5
  
  9
  
  10
  
  7
  
  6
  
  1
  
  12
  
  10
  
  17
  
  2
  
  i
  
  j
  
  3
  
  5
  
  2
  
  10
  
  7
  
  6
  
  1
  
  12
  
  10
  
  17
  
  9
  
  i
  
  j
  O’ng tamondan X dan katta bo’lmagan birinchi elementni topamiz.
  
• 
  Ikkalasining qiymatini almashtirzmiz.
  

10

5

9

10

7

6

1

12

3

17

2

i

j

3

3

5

2

10

7

6

1

12

10

17

9

i

j

3

5

2

1

7

6

10

12

10

17

9

i

j

3

5

2

1

7

6

10

12

10

17

9

i

j




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--;

}

}

if (L < j) qsort(L, j);

if (i < R) qsort(i, R);

}

int main() {

int n;

cin>>n;

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

cin>>a[i];

qsort(0, n-1);

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

cout<

return 0;

}

Agar bo’luvchi elementni o’rtadan emas, balki [L, R] kesmadan ixtiyoriy tanlab olinsa ishlash vaqti O(nlong(n)).

C++ dasturlash tilida saralash.

C++ da saralash juda oddiy Quick Sort bo’yicha saralaydi:

#include

#include

using namespace std;

int main() {

int n;

cin>>n;

int a[n];

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

cin>>a[i];

sort(a, a+n);

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

cout<

return 0;

}

Foydalanilgan adabiyotlar:

1. 
   Qudratxo’ja Musayev (“sralash algoritmlari”)
   
2. 
   Jahongir Soataliyev (sralash algoritmlarining 5 xil usuli)
   
3. 
   M.M.Aripov, N.A.Otaxanov (DASTURLASH ASOSLARI)