AlgorithmO #17 - Сортиране чрез сливане (Merge sort)

Днес ще ви покажа още един интересен алгоритъм за сортиране, който се нарича "Merge sort". Подобно на Quicksort, и този алгоритъм спада към категорията алгоритми "разделяй и владей" и е един от най-популярните и широко използваните.

Отново алгоритъм, който на пръв поглед изглежда страшен, но всъщност само трябва да го приложите няколко пъти, за да видите, че това е просто заблуда. 😉 По-трудната част тук е имплементацията на алгоритъма.

---

ОПИСАНИЕ:

Както казахме, това е един от най-популярните алгоритми за сортиране, със сложност (в най-лошия случай) O(n log n), правейки го подходящ за списъци с голям брой елементи (и неподходящ за списъци с малък брой елементи).

Идеята зад Mergesort лесно ще ни даде обяснението защо алгоритъмът е в категорията "разделяй и владей".
При него делим масива на части, които сортираме поотделно и накрая сливаме в един общ сортиран масив. Интересната част на този алгоритъм е в това как става самото сливане на тези отделни части.

Недостатък на Mergesort е, че изисква памет за допълнителен масив.

АЛГОРИТЪМ:

1. Делим масива на 2 части *
2. Повтаряме стъпка 1 за всеки подмасив докато не останат само подмасиви с по 1 елемент
3. Сливаме подмасивите в общ масив в сортиран ред

* Ако масивът има четен брой елементи - делим го на 2 равни части.
   Ако масивът има нечетен брой елементи - делим го на 2 части, като дясната част има с един елемент повече (т.е. средният елемент е в дясната част).

Как става сливането?

Сливаме 2 сортирани масива (във възходящ ред *):
- А[] с m елемента
- B[] с n елемента

... в 1 нов сортиран масив (отново във възходящ ред):
- C[] с m+n елемента

* За да сортираме масива в низходящ ред, просто трябва да променим знаците където е необходимо.

---

1.  Имаме 3 брояча:
- i - индекс на елемент в A[] (в началото i = 0)
- j - индекс на елемент в B[] (в началото j = 0)
- k - индекс на първи свободен елемент в C[]  (в началото k = 0)

2. Ако i < m и j < n:
      - избираме по-малкия елемент от A[i] и B[j]
      - записваме го в C[k]
   Иначе преминаваме към стъпка 4.

3. Увеличаваме k с 1.
      Ако A[i] <= B[j], увеличаваме i с 1.
      Иначе увеличаваме j с 1.
    Повтаряме стъпка 2.

4. Ако i < m, копираме останалите елементи от А[] в C[]
    Иначе копираме останалите елементи от B[] в C[]

ПРИМЕР:

Нека сортираме следния масив (във възходящ ред):

Индекс	0	1	2	3	4	5	6	7
Стойност	14	33	27	10	35	19	42	44

Този пример ще бъде едно истинско приключение. 😅

Първата ни стъпка е да разделим масива на две части. Сигурно сте забелязали, че всъщност можем да прескочим тази част и направо да разделим масива на 8 части и всяка част да има по 1 елемент от масива, но тук се опитваме да научим как работи имплементацията на Merge sort, която ще ползваме по-долу. 😉

Тъй като масивът е с четен брой елементи, разделяме го на две равни части (първата с елементи с индекс от 0 до 3 включително, втората с елементи с индекси от 4 до 7 включително).

За да е по-прегледно, нека представим масивите като множества:

 [ 14, 33, 27, 10 ] , [ 35, 19, 42, 44 ]

Повтаряме този процес (делим всяка част на нови 2 части), докато не стигнем положение в което имаме само масиви от по 1 елемент:

[ 14 , 33 ] , [ 27, 10 ] , [ 35, 19 ] , [ 42, 44 ]

Правим още едно разделяне на всяка част и стигаме до следното положение:

[ 14 ] , [ 33 ] , [ 27 ] , [ 10 ] , [ 35 ] , [ 19 ] , [ 42 ] , [ 44 ]

Сега стигнахме до интересната част. Как ще слеем тези подмасиви в един общ сортиран масив?

---

Итерация 1

Първо трябва да разберем, че всеки подмасив от 1 елемент автоматично е сортиран.

Нашият алгоритъм за сливане изисква да имаме 2 сортирани масива, които ще обединим в трети (крайния масив). Имаме такива, при това цели 8 от тях... 😢

Започваме с първите 2 подмасива. Приемаме, че първият ще е A[], а вторият B[], т.е
A = [ 14 ] и B = [ 33 ].

Нека, за да е по-прегледно, обозначим 2-та подмасива, които ще сливаме, с червен (A[]) и зелен цвят (B[]):

[ 14 ] , [ 33 ] , [ 27 ] , [ 10 ] , [ 35 ] , [ 19 ] , [ 42 ] , [ 44 ]

Когато елементите са по един, няма нужда да се задълбочаваме в това как работи алгоритъмът за сливане, а можем да го обобщим като:

- сравни елементите на 2-та подмасива и, ако не са във възходящ ред, ги размени

- обедини ги в един общ подмасив

Тъй като 14 < 33, няма да разменяме елементите, а направо ще ги обединим:

[ 14, 33 ] , [ 27 ] , [ 10 ] , [ 35 ] , [ 19 ] , [ 42 ] , [ 44 ]

Продължаваме със следващата двойка подмасиви, т.е. A = [ 27 ] и B = [ 10 ]:

[ 14, 33 ] , [ 27 ] , [ 10 ] , [ 35 ] , [ 19 ] , [ 42 ] , [ 44 ]

Виждаме, че 27 > 10, затова разменяме елементите и след това ги обединяваме в един общ подмасив:

[ 14, 33 ] , [ 10, 27 ] , [ 35 ] , [ 19 ] , [ 42 ] , [ 44 ]

Продължаваме със следващата двойка подмасиви, т.е. A = [ 35 ] и B = [ 19 ]:

[ 14, 33 ] , [ 10, 27 ] , [ 35 ] , [ 19 ] , [ 42 ] , [ 44 ]

Виждаме, че 35 > 19, затова разменяме елементите и след това ги обединяваме в един общ подмасив: 

[ 14, 33 ] , [ 10, 27 ] , [ 19, 35 ] , [ 42 ] , [ 44 ]

Продължаваме със следващата двойка подмасиви, т.е. A = [ 42 ] и B = [ 44 ]:

[ 14, 33 ] , [ 10, 27 ] , [ 19, 35 ] , [ 42 ] , [ 44 ]

Тъй като 42 < 44, няма да разменяме елементите, а направо ще ги обединим:

[ 14, 33 ] , [ 10, 27 ] , [ 19, 35 ] , [ 42, 44 ]

Приключихме с първата итерация на алгоритъма. 😉 Потупайте се по рамото, заслужихте го!

---

Итерация 2

Сега трябва да повторим същата процедура, но този път подмасивите ще са с по 2 елемента (сами виждате колко неефективно би било да използваме този алгоритъм за малки масиви).

И така, началното положение на подмасивите е следното:

[ 14, 33 ] , [ 10, 27 ] , [ 19, 35 ] , [ 42, 44 ]

Отново започваме с първите два подмасива, т.е. A = [ 14,  33 ] и B = [ 10, 27 ]:

[ 14, 33 ] , [ 10, 27 ] , [ 19, 35 ] , [ 42, 44 ]

Сега вече ще вкараме алгоритъма за сливане в действие. 😅 C[] ще бъде новият подмасив, който ще включва елементите на A и B в сортиран ред.

Първо казахме, че ще ни трябват няколко помощни променливи:

- i, j, k, m, n (вижте алгоритъма, ако не си спомняте коя за какво беше)

В началото i = 0, j = 0, k = 0.

Виждаме, че двата подмасива имат по 2 елемента, следователно m = 2 и n = 2.

Тъй като i < m и j < n, сравняваме A[i] с B[j] и виждаме, че това всъщност са елементите 14 и 10. Вземаме по-малкия (10) и го поставяме на място C[k], т.е. C = [ 10 ]. Увеличаваме k и j с 1 (защото по-малкият елемент се намираше в B[], а броячът на B е j). Сега i = 0, j = 1, k = 1.

Тъй като i < m и j < n (все още), сравняваме A[i] с B[j] и виждаме, че това всъщност са елементите 14 и 27. Вземаме по-малкия (14) от B[] и го поставяме на място C[k], т.е. C = [ 10, 14 ]. Увеличаваме k и i с 1. Сега i = 1, j = 1, k = 2.

Тъй като i < m и j < n (все още), сравняваме A[i] с B[j] и виждаме, че това всъщност са елементите 33 и 27. Вземаме по-малкия (27) от B[] и го поставяме на място C[k], т.е. C = [ 10, 14, 27 ]. Увеличаваме k и j с 1. Сега i = 1, j = 2, k = 3.

Виждаме, че i < m, но j = n, затова отиваме към стъпка 4 от алгоритъма за сливане. Тя гласи, че ако i < m, трябва да прехвърлим останалите елементи от A[] в C[]. Имаме само един останал елемент в A[] (33), така че след сливането, C = [ 10, 14, 27, 33 ].

Както виждаме, сляхме подмасивите в един общ сортиран подмасив. 😉 Ще следваме този принцип за сливане и по-нататък. Сега подмасивите ще изглеждат така:

[ 10, 14, 27, 33 ] , [ 19, 35 ] , [ 42, 44 ]

Продължаваме по същия начин за следващата двойка подмасиви:

[ 10, 14, 27, 33 ] , [ 19, 35 ] , [ 42, 44 ]

Вече знаете процедурата. 😛 Единствената разлика е, че този път A = [ 19, 35 ] и B = [ 42, 44 ]. В началото (отново) i = 0, j = 0, k = 0. Виждаме, че m = 2 и n = 2. Ще започнем с празен масив C[], в който ще добяваме сортираните елементи от двата подмасива.

След като приложим същия алгоритъм за тези два подмасива, ще получим следните два по-големи подмасива:

[ 10, 14, 27, 33 ] , [ 19, 35, 42, 44 ]

---

Итерация 3

По абсолютно същия начин ще слеем и последните два (вече сортирани) подмасива в един общ сортиран масив (крайната ни цел). Ако сте стигнали дотук, трябва да се почерпите с нещо! 😁

Сега подмасивите изглеждат така:

[ 10, 14, 27, 33 ] , [ 19, 35, 42, 44 ]

Остава да ги слеем.

Виждаме, че A = [ 10, 14, 27, 33 ] и B = [ 19, 35, 42, 44 ].

Декларираме 3 брояча - i = j = k = 0.
Броят на елементите на A[] е 4, затова m = 4.
Броят на елементите на B[] е 4, затова n = 4.

Тъй като i < 4 и j < 4:
- сравняваме A[i] с B[j] (10 и 19)
- вземаме по-малкия елемент (10)
- поставяме го в C[k], т.е. C = [ 10 ]
- увеличаваме k с 1
- увеличаваме i с 1
- сега i = 1, j = 0, k = 1

Продължаваме по същия начин до пълно сливане.

Тъй като i < 4 и j < 4:
- сравняваме A[i] с B[j] (14 и 19)
- вземаме по-малкия елемент (14)
- поставяме го в C[k], т.е. C = [ 10, 14 ]
- увеличаваме k с 1
- увеличаваме i с 1
- сега i = 2, j = 0, k = 2

Тъй като i < 4 и j < 4:
- сравняваме A[i] с B[j] (27 и 19)
- вземаме по-малкия елемент (19)
- поставяме го в C[k], т.е. C = [ 10, 14, 19 ]
- увеличаваме k с 1
- увеличаваме j с 1
- сега i = 2, j = 1, k = 3

Тъй като i < 4 и j < 4:
- сравняваме A[i] с B[j] (27 и 35)
- вземаме по-малкия елемент (27)
- поставяме го в C[k], т.е. C = [ 10, 14, 19, 27 ]
- увеличаваме k с 1
- увеличаваме i с 1
- сега i = 3, j = 1, k = 4

Тъй като i < 4 и j < 4:
- сравняваме A[i] с B[j] (33 и 35)
- вземаме по-малкия елемент (33)
- поставяме го в C[k], т.е. C = [ 10, 14, 19, 27, 33 ]
- увеличаваме k с 1
- увеличаваме i с 1
- сега i = 4, j = 1, k = 5

Вече i == 4, затова остава само да добавим останалите елементи на B[] в C[].

Останалите елементи на B[] са тези с индекс от 1 до 3 включително.

Крайният масив ще изглежда така: C = [ 10, 14, 19, 27, 33, 35, 42, 44 ]

Или, за да сме по-модерни, ще изглежда така 😅:

Индекс	0	1	2	3	4	5	6	7
Стойност	10	14	19	27	33	35	42	44

ИМПЛЕМЕНТАЦИЯ (Java):

	public class MergeSort {
	public static int[] mergeSort(int[] arr) { // Note that arr[] will play the role of C[]
	if (arr.length > 1) {
	int m = arr.length / 2;
	int n = arr.length - m;
	int[] A = new int[m];
	int[] B = new int[n];
	// Fill A[]
	for (int p = 0; p < m; ++p) {
	A[p] = arr[p];
	}
	// Fill B[]
	int q = 0;
	for (int p = m; p < arr.length; ++p) {
	B[q] = arr[p];
	q++;
	}
	// Recursively split and sort both sub-arrays
	A = mergeSort(A);
	B = mergeSort(B);
	// Merge sub-arrays
	int i = 0;
	int j = 0;
	int k = 0;
	while (i < m && j < n) {
	if (A[i] <= B[j]) {
	arr[k] = A[i];
	k++;
	i++;
	}
	else {
	arr[k] = B[j];
	k++;
	j++;
	}
	}
	if (i < m) {
	// Add the rest of A[]'s elements to arr[]
	for (int p = i; p < m; ++p) {
	arr[k] = A[p];
	k++;
	}
	}
	else {
	// Add the rest of B[]'s elements to arr[]
	for (int p = j; p < n; ++p) {
	arr[k] = B[p];
	k++;
	}
	}
	}
	return arr;
	}
	public static void main(String[] args) {
	int[] arr = new int[] { 14, 33, 27, 10, 35, 19, 42, 44 };
	arr = mergeSort(arr);
	for (int element : arr) {
	System.out.print(element + " ");
	}
	}
	}

view raw ALGORITHMO-17-Merge-Sort-Implementation.java hosted with ❤ by GitHub

---

Това е за днес! Ако видите някоя грешка - споделете, няма да ви се обидя! 😅