Отново алгоритъм, който на пръв поглед изглежда страшен, но всъщност само трябва да го приложите няколко пъти, за да видите, че това е просто заблуда. 😉 По-трудната част тук е имплементацията на алгоритъма.
---
ОПИСАНИЕ:
Както казахме, това е един от най-популярните алгоритми за сортиране, със сложност (в най-лошия случай) 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
Нашият алгоритъм за сливане изисква да имаме 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 ]
След като приложим същия алгоритъм за тези два подмасива, ще получим следните два по-големи подмасива:
[ 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
|
---
Това е за днес! Ако видите някоя грешка - споделете, няма да ви се обидя! 😅
Няма коментари:
Публикуване на коментар