Reja: kirish I. Bob. Saralash algoritimi haqida tushuncha

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:

Ajratish va g'alaba qozonish strategiyasi
Divide and Conquer texnikasi yordamida biz muammoni subtasksga ajratamiz. Bizda har bir kichik topshiriq uchun echim bo'lsa, biz asosiy vazifani hal qilish uchun pastki vazifalardan olingan natijalarni "birlashtiramiz".

Aytaylik, biz A massivini saralashni xohladik. Sub-vazifa bu qatorning kichik qismini, p indeksidan boshlanib, r indeksiga qadar A [p..r] deb belgilangan tartiblashtirishdan iborat bo'ladi.

Bo'lmoq
Agar q p va r orasidagi oraliq nuqta bo'lsa, unda biz A [p..r] kichik qatorni ikkita A [p..q] va A [q + 1, r] qatorlarga bo'lishimiz mumkin.

Hukmronlik qiling

Fath bosqichida biz ikkala A [p..q] va A [q + 1, r] kichik dasturlarni saralashga harakat qilamiz. Agar biz hali ham boshlang'ich darajaga etib bormagan bo'lsak, biz yana ikkala quyi qismni ajratib, ularni saralashga harakat qilamiz.

Biz birlashtiramiz

Fath etuvchi pog'ona tayanch pog'onasiga etganida va biz A [p..r] massivi uchun ikkita tartiblangan A [p..q] va A [q + 1, r] kichik majmualarni olsak, natijalarni birlashtiramiz, tartiblangan massiv hosil qilamiz. A [p .r] ikkita saralangan A [p..q] va A [q + 1, r]

Birlashtirish tartiblash algoritmi

MergeSort funktsiyasi qatorni ketma-ket ikkiga ajratadi, biz 1-darajali subarrayda MergeSort-ga o'tishga harakat qiladigan bosqichga yetguncha. p == r.
Shundan so'ng, birlashma funktsiyasi ishga tushadi, bu tartiblangan massivlarni butun massiv birlashguncha katta massivlarga birlashtiradi.

1. 
   MergeSort(A, p, r)
   
2. 
   If p > r
   
3. 
   return;
   
4. 
   q = (p+r)/2;
   
5. 
   mergeSort(A, p, q)
   
6. 
   mergeSort(A, q+1, r)
   
7. 
   merge(A, p, q, r)
   

Butun qatorni saralash uchun biz MergeSort (A, 0, length (A) -1) ga qo'ng'iroq qilishimiz kerak.
Quyidagi rasmda ko'rsatilgandek, birlashtirish tartiblash algoritmi 1 elementli massivning asosiy holatiga kelgunimizcha qatorni rekursiv ravishda ikkiga bo'linadi. Keyin birlashtirish funktsiyasi saralangan ichki massivlarni tanlaydi va ularni birlashtirib butun massivni asta-sekin saralashga imkon beradi.

Birlashtirish bosqichi bo'yicha birlashtirish
Har bir rekursiv algoritm asosiy holatga va asosiy holatlar natijalarini birlashtirish qobiliyatiga bog'liq. birlashtirish tartiblash istisno emas. Algoritmning eng muhim qismi bu "birlashtirish" bosqichidir.

Birlashish bosqichi bitta katta tartiblangan ro'yxat (massiv) yaratish uchun ikkita tartiblangan ro'yxatni (massivlarni) birlashtirishning oddiy masalasini hal qilishdan iborat.

Algoritm uchta ko'rsatkichni saqlaydi, ikkitasi har biri uchun va bittasi tartiblangan qatorning joriy indeksini saqlab qolish uchun.

Ikkinchi qatorda boshqa elementlar qolmaganligi va ikkala massiv ham ishga tushirilganda saralanganligini bilganimiz sababli, qolgan qatorlarni to'g'ridan-to'g'ri birinchi qatordan nusxalashimiz mumkin.

Birlashtirish algoritmi uchun kod yozish
Biz yuqorida tavsiflangan birlashish bosqichi bilan birlashma tartiblash uchun foydalanadigan farq o'rtasidagi farq shundan iboratki, birlashish funktsiyasi faqat ketma-ket ichki massivlarda bajariladi.

Shuning uchun biz faqat qatorga, birinchi pozitsiyaga, birinchi subarrayning oxirgi indeksiga (ikkinchi subarrayning birinchi indeksini hisoblashimiz mumkin) va ikkinchi subarrayning oxirgi indeksiga muhtojmiz.

Bizning vazifamiz ikkita A [p..q] va A [q + 1..r] kichik massivlarni birlashtirib, tartiblangan A [p..r] massivini yaratishdir. Shunday qilib A, p, q va r funktsiyalar uchun kirish ma'lumotlari

Birlashtirish funktsiyasi quyidagicha ishlaydi:

L ← A [p..q] va M ← A [q + 1..r] kichik jadvallarining nusxalarini yarating.

I, j va k uchta ko'rsatkichni yarating
i 1dan boshlangan joriy L indeksini saqlayman
j joriy indeksni 1 dan boshlab saqlaydi
k p dan boshlangan joriy A [p..q] indeksini saqlaydi
L yoki M oxiriga etgunimizcha L va M dan kattaroq elementlarni tanlang va ularni A [p..q] holatiga joylashtiring.
L yoki Mdagi elementlarimiz tugagach, qolgan elementlarni oling va A [p..q] ga joylashtiring.
Kodda shunday bo'ladi:

1. 
   void merge(int A[], int p, int q, int r)
   
2. 
   {
   
3. 
   /* Создание L ← A[p..q] и M ← A[q+1..r] */
   
4. 
   int n1 = q - p + 1;
   
5. 
   int n2 = r - q;
   
6. 
   
7. 
   int L[n1], M[n2];
   
8. 
   
9. 
   for (i = 0; i < n1; i++)
   
10. 
    L[i] = A[p + i];
    
11. 
    for (j = 0; j < n2; j++)
    
12. 
    M[j] = A[q + 1 + j];
    
13. 
    
14. 
    /* Ichki qatorlar va asosiy massivning joriy indeksini saqlash */
    
15. 
    int i, j, k;
    
16. 
    i = 0;
    
17. 
    j = 0;
    
18. 
    k = p;
    
19. 
    
20. 
    
21. 
    /* L yoki M oxiriga yetgunimizcha L va M elementlarning kattaroq qismini tanlang va ularni A nuqtada to'g'ri joyga qo'ying [p..r]*/
    
22. 
    while (i < n1 && j < n2)
    
23. 
    {
    
24. 
    if (L[i] <= M[j])
    
25. 
    {
    
26. 
    arr[k] = L[i];
    
27. 
    i++;
    
28. 
    }
    
29. 
    else
    
30. 
    {
    
31. 
    arr[k] = M[j];
    
32. 
    j++;
    
33. 
    }
    
34. 
    k++;
    
35. 
    }
    
36. 
    
37. 
    /* L yoki Mdagi elementlarimiz tugagach, qolgan elementlarni oling va A ga joylashtiring [p..r]*/
    
38. 
    while (i < n1)
    
39. 
    {
    
40. 
    A[k] = L[i];
    
41. 
    i++;
    
42. 
    k++;
    
43. 
    }
    
44. 
    
45. 
    while (j < n2)
    
46. 
    {
    
47. 
    A[k] = M[j];
    
48. 
    j++;
    
49. 
    k++;
    
50. 
    }
    
51. 
    }