Birlashtirish orqali saralash(Merge sort) algoritmlari. Birlashtirish orqali saralash(Merge sort)

Birlashtirish orqali saralash(Merge sort) algoritmlari.

Birlashtirish orqali saralash(Merge sort)

Bu algoritm Jon fon Neyman

tomonidan 1946 yilda taklif qilingan.

Bo’lib tashla va hukmronlik qil

Metodi ga asoslanadi.

Ishlash vaqti O(nlog(n))

“Bo’lib tashla va hukmronlik qil metodi” – katta masalani yechib bo’lmasa uni bo’laklarga ajratiladi va kichik bo’laklar alohida yechiladi.

Kichik bo’laklar yechimlaridan foydalanib katta masalaning yechimi hosil qilinadi.

Birlashtirish orqali saralash(2)

• Ikkita saralangan massivni birlashtirish masalasi.

5

8

15

29

32

7

18

20

25

5

7

8

15

18

20

25

29

32

Birlashtirish orqali saralash(3)

Birlashtirish orqali saralash(4)

• Birlashtirish orqali saralash uchun berilgan massivni ikki qismga ajratadi, qismlar alohida saralanadi, saralangan qismlarni birlashtiriladi.

•  

a massivning [L, m] va [m+1, R] qismlarini birlashtirish

• int p1 = L, p2 = m+1;
• int p = L;
• while (p1 <= m && p2 <= R) {
• if (a[p1] <= a[p2]) {
• b[p] = a[p1];
• p++;
• p1++;
• }
• else {
• b[p] = a[p2];
• p++;
• p2++;
• }
• }

while (p1 <= m) {

• while (p1 <= m) {
• b[p] = a[p1];
• p++;
• p1++;
• }
• while (p2 <= R) {
• b[p] = a[p2];
• p++;
• p2++;
• }
• for (int i = L; i <= R; i++)
• a[i] = b[i];

Birlashtirish orqali saralash(5) Misol

Birlashtirish orqali saralash(6). mergesort rekursiv funksiyasi

• void mergesort(int L, int R) {
• if (L >= R)
• return;
• int m = (L+R) / 2;
• mergesort(L, m);
• mergesort(m+1, R);
• //Birlashtirish yoziladi
• }
• Asosiy qismda: mergesort(1, n);

Birlashtirish orqali saralash ishlash vaqti nlog(n)

• Savollar?