Triedenie zlučovaním
Verzia z 10:33, 25. marec 2021, ktorú vytvoril Filip Tomek (diskusia | príspevky) (→Vlastnosti algoritmu)
Obsah
Zlučovací algoritmus Merge
Princíp zlučovania tkvie v tom, že na vstupe prijmeme dva alebo viac utriedených zoznamov, ktoré skombinuje do jedného výstupného utriedeného zoznamu. Výstupný zoznam musí obsahovať všetky prvky z oboch vstupných zoznamov. Zoznam môže byť reprezentovaný ako dátová štruktúra pole alebo aj ako lineárny zoznam. V tejto časti sa zameriame na algoritmus pre dátovú štruktúru pole.
Algoritmus Merge tvorí dôležitú časť triediaceho algoritmu MergeSort.
Slovný opis algoritmu
Máme pole, ktoré sa skladá z dvoch už utriedených polovíc. Vytvoríme dve pomocné polia L a P, do ktorých skopírujeme obsahy oboch polovíc. Potom súčasne prechádzame obe pomocné polia a vždy z uvažovanej dvojice prvkov vyberáme ten menší z nich (keď triedime od najmenšieho po najväčší). Tento prvok potom vložíme na prvú voľnú pozíciu vstupného poľa. Index vstupného poľa zvyšujeme vždy, keď doňho vložíme nejaký prvok a pri pomocnomých poliach zasa vtedy, keď z nich prvok vyberáme. Ak nastane situácia, že z jedného pomocného poľa vyberieme všetky prvky skôr, ako z druhého pomocného poľa, potom zbytok druhého pomocného poľa už iba pridávame na koniec do vstupného poľa.
Vlastnosti algoritmu
- vhodný pre dátové štruktúry: pole, lineárny zoznam
- časová náročnosť: vždy lineárna [math] O(n) [/math]
- priestorová náročnosť: lineárna [math]O(n)[/math] pre pole (alokovanie dočasných polí), [math]O(1)[/math] pre lineárny zoznam (výmena smerníkov)
- využitie: podprogram pre triediaci algoritmus MergeSort
Pseudokód
Nech funkcia Merge má nasledovný prototyp: Merge(pole[], lavy, stred, pravy)
- 1. Je
lavy >= pravy ? Ak áno, skonči, inak pokračuj krokom 2. - 2. Nech:
i = 0, j = 0, k = lavy - 3. Nech:
dlzka_L = stred - lavy + 1, dlzka_P = pravy - stred - 4. Nech:
L = pole[lavy ... stred], P = pole[stred + 1 ... pravy] - 5. Je
i < dlzka_La zároveňj < dlzka_P? Ak áno, pokračuj krokom 5.1., inak skoč na krok 6.- 5.1. Je
L[i] <= P[j]?- Ak áno:
- 5.1.1.
pole[k] = L[i] - 5.1.2
k += 1 - 5.1.3
i += 1 - 5.1.4 skoč na krok 5.
- 5.1.1.
- Ak nie:
- 5.1.1.
pole[k] = P[j] - 5.1.2.
k += 1 - 5.1.3.
j += 1 - 5.1.4. skoč na krok 5.
- 5.1.1.
- Ak áno:
- 5.1. Je
- 6. Je
i < dlzka_L? Ak áno, pokračuj krokom 6.1., inak skoč na krok 7.- 6.1.
pole[k] = L[i] - 6.2.
k += 1 - 6.3.
i += 1 - 6.4. Skoč na krok 6.
- 6.1.
- 7. Je
j < dlzka_P? Ak áno, pokračuj krokom 7.1., inak skonči.- 7.1.
pole[k] = P[j] - 7.2.
k += 1 - 7.3.
j += 1 - 7.4. Skok na krok 7.
- 7.1.
Merge sort
Merge Sort je triediaci algoritmus, ktorý je založený na princípe "rozdeľ a panuj", čo znamená, že pole najskôr rozdelí na dve polovice, tie zoradí a potom ich zlúči naspäť dokopy. Keďže najhoršia doba výpočtu je [math]O(n.log(n))[/math], tak sa radí medzi najpoužívanejšie a najviac rešpektované triediacie algoritmy.
Princíp algoritmu
Algoritmus Merge vykonáva 4 základné úlohy:
- Delenie poľa na dve polovice.
- Triedenie ľavej polovice poľa.
- Triedenie pravej polovice poľa.
- Zlúčenie oboch polovíc pomocou funkcie Merge.
Vlastnosti algoritmu
- vhodný pre dátové štruktúry: pole, lineárny zoznam
- časová náročnosť: vždy linearitmická [math] O(n.log(n)) [/math]
- priestorová náročnosť: lineárna [math]O(n)[/math] pre pole (alokovanie dočasných polí), konštantná [math]O(1)[/math] pre lineárny zoznam (výmena smerníkov)
- druh triedenia: triedenie zlučovaním (komparačný algoritmus)
- stabilita triedenia: stabilný
- miesto triedenia: externé triedenie (vhodný na triedenie veľkých objemov dát uložených na disku)
Slovný opis algoritmu - treba refaktorovať
Pri zavolaní funkcie MergeSort, jej program pošle 3 údaje: pole, ktoré chceme zoradiť, index prvého prvku daného pola a index posledného prvku pola. Funkcia si vypočíta index prostredného prvku pola (pri nepárnom počte prvkov pola je to index prvku, ktorý sa vypočíta ako dĺžka_pola / 2, a táto hodnota je zaokrúhlená nadol) a podľa tohto prvku pole rozdelí na ľavú a pravú časť. Vo vnútri funkcie sa nachádzajú dve rekurzívne volania, a to pre ľavú časť pola a pre pravú časť pola. Tento cyklus sa opakuje dokým novovzniknuté polia nemajú práve 1 prvok. Akonáhle majú vzniknuté polia 1 prvok, tak sa ukončí rekurzívne volanie a nastupuje volanie funkcie Merge. Funkcia Merge bude vzniknuté polia postupne spájať dokopy, pričom prvky daných polí usporiada vzostupne. Výsledkom funkcie MergeSort je pole s uporiadanými prvkami.
Pseudokód
Nech nech má funkcia MergeSort nasledovný prototyp: MergeSort(pole[], lavy, pravy)
- 1. Je
lavy >= pravy? Ak áno, skonči volanie, inak pokračuj krokom 2. - 2. Nech:
stred = lavy + (pravy - lavy) / 2, pričom znak / vyjadruje celočíselné delenie. - 3. Rekurzívne zavolaj funkciu
MergeSort(pole[], lavy , stred) - 3. Rekurzívne zavolaj funkciu
MergeSort(pole[], stred + 1 , pravy) - 4. Zavolaj funkciu
Merge(pole[], lavy, stred, pravy) - 5. Skonči volanie.
Implementácia algoritmov Merge a MergeSort
C
1 void Merge(int pole[], int lavy, int stred, int pravy);
2 void MergeSort(int pole[], int lavy, int pravy);
3
4 /* hlavný program */
5
6 int main()
7 {
8 int pole[] = {12, 11, 13, 5, 6, 7};
9 int dlzka_pola = sizeof(pole) / sizeof(pole[0]);
10
11 printf("Pôvodné pole: \n");
12
13 for (int i = 0; i < dlzka_pola; ++i)
14 {
15 printf("%d ", pole[i]);
16 }
17
18 MergeSort(pole, 0, dlzka_pola - 1);
19
20 printf("\nUtriedené pole: \n");
21
22 for (int i = 0; i < dlzka_pola; ++i)
23 {
24 printf("%d ", pole[i]);
25 }
26
27 return 0;
28 }
29
30 void Merge(int pole[], int lavy, int stred, int pravy)
31 {
32 /* ak má pole menej ako 2 prvky, skonči */
33
34 if (lavy >= pravy)
35 {
36 return;
37 }
38
39 /* vyrátaj dĺžky oboch polovíc poľa */
40
41 int L_dlzka = stred - lavy + 1;
42 int P_dlzka = pravy - stred;
43
44 /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */
45
46 int *L = (int*)malloc(L_dlzka * sizeof(int));
47 int *P = (int*)malloc(P_dlzka * sizeof(int));
48
49 /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */
50
51 int i, j, k;
52
53 /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */
54
55 for (i = 0; i < L_dlzka; ++i)
56 {
57 L[i] = pole[lavy + i];
58 }
59
60 for (j = 0; j < P_dlzka; ++j)
61 {
62 P[j] = pole[stred + 1 + j];
63 }
64
65 /* nastav indexy na začiatok daných polí */
66
67 i = 0; j = 0; k = lavy;
68
69 /* zlučuj dočasné polia L a P do finálneho poľa pole */
70
71 while(i < L_dlzka && j < P_dlzka)
72 {
73 if(L[i] <= P[j])
74 {
75 pole[k++] = L[i++];
76 }
77 else
78 {
79 pole[k++] = P[j++];
80 }
81 }
82
83 /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */
84
85 while(i < L_dlzka)
86 {
87 pole[k++] = L[i++];
88 }
89
90 /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */
91
92 while(j < P_dlzka)
93 {
94 pole[k++] = P[j++];
95 }
96
97 /* uvoľni použitú pamäť */
98
99 free(L);
100 free(P);
101 }
102
103 void MergeSort(int pole[], int lavy, int pravy)
104 {
105 /* ak má pole menej ako 2 prvky, skonči volanie */
106
107 if(lavy >= pravy)
108 {
109 return;
110 }
111 /* urči si prostredný index */
112
113 int stred = lavy + (pravy - lavy) / 2;
114
115 /* utrieď ľavú polovicu poľa */
116
117 MergeSort(pole, lavy, stred);
118
119 /* utrieď pravú polovicu poľa */
120
121 MergeSort(pole, stred+1, pravy);
122
123 /* zlúč obe polovice dokopy */
124
125 Merge(pole, lavy, stred, pravy);
126 }
C++
1 #include <iostream>
2
3 using std::cout;
4 using std::endl;
5
6 void Merge(int pole[], int lavy, int stred, int pravy);
7 void MergeSort(int pole[], int lavy, int pravy);
8
9 /* hlavný program */
10
11 int main()
12 {
13 int pole[] = {12, 11, 13, 5, 6, 7};
14 int dlzka_pola = sizeof(pole) / sizeof(pole[0]);
15
16 printf("Pôvodné pole: \n");
17
18 for (auto i: pole)
19 {
20 cout<<i<<" ";
21 }
22
23 MergeSort(pole, 0, dlzka_pola - 1);
24
25 cout<<endl<<"Utriedené pole:"<<endl;
26
27 for (auto i: pole)
28 {
29 cout<<i<<" ";
30 }
31
32 return 0;
33 }
34
35 void Merge(int pole[], int lavy, int stred, int pravy)
36 {
37 /* ak má pole menej ako 2 prvky, skonči */
38
39 if (lavy >= pravy)
40 {
41 return;
42 }
43
44 /* vyrátaj dĺžky oboch polovíc poľa */
45
46 int L_dlzka = stred - lavy + 1;
47 int P_dlzka = pravy - stred;
48
49 /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */
50
51 int *L = new int[L_dlzka];
52 int *P = new int[P_dlzka];
53
54 /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */
55
56 int i, j, k;
57
58 /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */
59
60 for (i = 0; i < L_dlzka; ++i)
61 {
62 L[i] = pole[lavy + i];
63 }
64
65 for (j = 0; j < P_dlzka; ++j)
66 {
67 P[j] = pole[stred + 1 + j];
68 }
69
70 /* nastav indexy na začiatok daných polí */
71
72 i = 0; j = 0; k = lavy;
73
74 /* zlučuj dočasné polia L a P do finálneho poľa pole */
75
76 while(i < L_dlzka && j < P_dlzka)
77 {
78 if(L[i] <= P[j])
79 {
80 pole[k++] = L[i++];
81 }
82 else
83 {
84 pole[k++] = P[j++];
85 }
86 }
87
88 /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */
89
90 while(i < L_dlzka)
91 {
92 pole[k++] = L[i++];
93 }
94
95 /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */
96
97 while(j < P_dlzka)
98 {
99 pole[k++] = P[j++];
100 }
101
102 /* uvoľni použitú pamäť */
103
104 delete []L;
105 delete []P;
106 }
107
108 void MergeSort(int pole[], int lavy, int pravy)
109 {
110 /* ak má pole menej ako 2 prvky, skonči volanie */
111
112 if(lavy >= pravy)
113 {
114 return;
115 }
116 /* urči si prostredný index */
117
118 int stred = lavy + (pravy - lavy) / 2;
119
120 /* utrieď ľavú polovicu poľa */
121
122 MergeSort(pole, lavy, stred);
123
124 /* utrieď pravú polovicu poľa */
125
126 MergeSort(pole, stred+1, pravy);
127
128 /* zlúč obe polovice dokopy */
129
130 Merge(pole, lavy, stred, pravy);
131 }
Java
1 class MergeSort {
2 /* Zlúči 2 subpolia, ktoré sa vytvorili z pôvodného pola.
3 * Každé subpole má polovičnú dĺžku pôvodného pola.
4 * subpole1 [ľavý..stred]
5 * subpole2 [stred+1..pravý] */
6 void merge(int[] pole, int lavy, int stred, int pravy) {
7 // Výpočet dĺžky 2 subpolí
8 int n1 = stred - lavy + 1;
9 int n2 = pravy - stred;
10
11 // Vytvorenie pomocných polí
12 int[] L = new int[n1];
13 int[] P = new int[n2];
14
15 // Načítanie dát do pomocných polí
16 for (int i = 0; i < n1; i++)
17 L[i] = pole[lavy + i];
18
19 for (int j = 0; j < n2; j++)
20 P[j] = pole[stred + 1 + j];
21
22 // Počiatočné indexy prvého a druhého subpola
23 int i = 0, j = 0;
24 // Počiatočný index zlúčeného subpola
25 int k = lavy;
26
27 // Zlúčenie dvoch podpolí
28 while (i < n1 && j < n2) {
29 if (L[i] <= P[j]) {
30 pole[k] = L[i];
31 i++;
32 }
33 else {
34 pole[k] = P[j];
35 j++;
36 }
37 k++;
38 }
39
40 /* V prípade, že v jednom zo subpolí sa nachádzajú prvky, ktoré neboli zlúčené do pola,
41 * tak sa do pola jednoducho skopírujú */
42 while (i < n1) {
43 pole[k] = L[i];
44 i++;
45 k++;
46 }
47
48 while (j < n2) {
49 pole[k] = P[j];
50 k++;
51 j++;
52 }
53 }
54
55 /* Funkcia, ktorá zoradí pole použitím funkcie merge() */
56 void sort (int[] pole, int lavy, int pravy) {
57 if (lavy < pravy) {
58 //Musíme nájsť stred pola
59 int stred = lavy + (pravy - lavy) / 2;
60
61 // Zoradíme prvú a druhú polovicu pola samostatne
62 sort(pole, lavy, stred);
63 sort(pole, stred + 1, pravy);
64
65 // Zlúčime zoradené polovice do jedného pola
66 merge(pole, lavy, stred, pravy);
67 }
68 }
69 }
70
71 public class Main {
72 /* Funkcia na výpis pola dĺžky n */
73 static void vypis_pole(int[] pole) {
74 int n = pole.length;
75
76 for (int i = 0; i < n; i++) {
77 System.out.print(pole[i] + " ");
78 }
79 System.out.println();
80 }
81
82 /* Hlavný program */
83 public static void main(String[] args) {
84 int[] pole = {12, 11, 13, 5, 6, 7};
85
86 System.out.println("Zadané pole:");
87 vypis_pole(pole);
88
89 MergeSort ms = new MergeSort();
90 ms.sort(pole, 0, pole.length - 1);
91
92 System.out.println("\nZoradené pole:");
93 vypis_pole(pole);
94 }
95 }
Python3
1 def MergeSort(pole):
2 if len(pole) > 1:
3 # Nájdenie stredu pola
4 # zápis len(pole)//2 znamená, že dĺžka pola sa vydelí 2 a výsledok je celé číslo
5 stred = len(pole) // 2
6
7 # Rozdelenie pola na dve časti
8 L = pole[:stred]
9 P = pole[stred:]
10
11 # Zoradenie najskôr prvej časti pola, potom druhej
12 MergeSort(L)
13 MergeSort(P)
14
15 i = j = k = 0
16
17 # Načítanie dát do pomocných polí L[] a P[]
18 while i < len(L) and j < len(P):
19 if L[i] < P[j]:
20 pole[k] = L[i]
21 i += 1
22 else:
23 pole[k] = P[j]
24 j += 1
25 k += 1
26
27 # Kontrola či všetky prvky boli zlúčené dokopy,
28 # ak nie, tak sa do zlúčeného pola jednoducho skopírujú
29 while i < len(L):
30 pole[k] = L[i]
31 i += 1
32 k += 1
33
34 while j < len(P):
35 pole[k] = P[j]
36 j += 1
37 k += 1
38
39
40 # Kód na výpis pola
41 def vypis_pole(pole):
42 for i in range(len(pole)):
43 print(pole[i], end=" ")
44 print()
45
46
47 # Hlavný program
48 if __name__ == '__main__':
49 pole = [12, 11, 13, 5, 6, 7]
50 print("Zadané pole:", end="\n")
51 vypis_pole(pole)
52 MergeSort(pole)
53 print("Zoradené pole:", end="\n")
54 vypis_pole(pole)
