Jizzax filiali mustaqil ish

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

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.


17

10

5

9

3

7

6

1

12

3

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.
  

j

17

3

12

2

1

6

7

10

9

5

i

10



3



7

3

5

2

10

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