Mavazu: Saralash tushunchasi va algoritmi. Tanlash orqali saralash va uning qo’llanilishi

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 = 0; i < n-1; i++) {

int minPos = i;

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

if (a[j] < a[minPos])

minPos = j;

int t = a[i];

a[i] = a[minPos];

a[minPos] = t;

}

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

cout<

}

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

Pufakcha usulida saralash(Bubble sort).

• 
  
  Agar ikki qo’shni element noto’g’ri tartibda joylashib qolgan bo’lsa, ularning o’rnini almashtiramiz.
  
• 
  
  Umumiy n-1 marta jarayon bajariladi. Har safar ikkita qo’shni element taqqoslanadi.
  
• 
  
  Elementlar o’z o’rinlariga pufakga o’xshab siljib boradi.
  

3

5

2

10

9

4

3

2

5

10

9

4

3

2

5

9

10

4

3

2

5

9

4

10

3

2

5

9

4

10

2

3

5

9

4

10

2

3

5

4

9

10

2

3

5

4

9

10

2

3

4

5

9

10

2

3

4

5

9

10

2

3

4

5

9

10

2

3

4

5

9

10

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 .
  

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:



min

5

8

15

29

32

7

18

20

25

8

15

29

32

7

18

20

25

5

5

8

15

29

32

7

18

20

25

5

5

7

8

15

29

32

7

18

20

25

5

5

7

8

15

29

32

7

18

20

25

5

5

7

8

8

15

29

32

7

18

20

25

5

5

7

8

15

8

15

29

32

7

18

20

25

5

5

7

8

15

18
8

15

29

32

7

18

20

25

5

5

7

8

15

18

20

8

15

29

32

7

18

20

25

5

5

7

8

15

18

20

25
29

8

15

29

32

7

18

20

25

5

5

7

8

15

18

20

25

8

15

29

32

7

18

20

25

5

5

7

8

15

18

20

25

29

32

L

R

m

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

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)
   

http://fayllar.org