(Първо публикувано на 23.01.2017)
Днес ще ви покажа още един интересен алгоритъм за сортиране, който се нарича “Merge sort”. Подобно на Quicksort, и този алгоритъм спада към категорията алгоритми “разделяй и владей” и е един от най-популярните и широко използваните.
Отново алгоритъм, който на пръв поглед изглежда страшен, но всъщност само трябва да го приложите няколко пъти, за да видите, че това е просто заблуда. 😉 По-трудната част тук е имплементацията на алгоритъма.
ОПИСАНИЕ:
Както казахме, това е един от най-популярните алгоритми за сортиране, със сложност (в най-лошия случай) O(n log n), правейки го подходящ за списъци с голям брой елементи (и неподходящ за списъци с малък брой елементи).
Идеята зад Mergesort лесно ще ни даде обяснението защо алгоритъмът е в категорията “разделяй и владей”.
При него делим масива на части, които сортираме поотделно и накрая сливаме в един общ сортиран масив. Интересната част на този алгоритъм е в това как става самото сливане на тези отделни части.
Недостатък на Mergesort е, че изисква памет за допълнителен масив.
АЛГОРИТЪМ:
- Делим масива на 2 части (*)
- Повтаряме стъпка 1 за всеки подмасив докато не останат само подмасиви с по 1 елемент
- Сливаме подмасивите в общ масив в сортиран ред
(*) Ако масивът има четен брой елементи — делим го на 2 равни части. Ако масивът има нечетен брой елементи — делим го на 2 части, като дясната част има с един елемент повече (т.е. средният елемент е в дясната част).
Как става сливането?
Сливаме 2 сортирани масива (във възходящ ред (**)):
- А[] с m елемента
- B[] с n елемента
… в 1 нов сортиран масив (отново във възходящ ред):
- C[] с m+n елемента
(**) За да сортираме масива в низходящ ред, просто трябва да променим знаците където е необходимо.
—
Имаме 3 брояча:
- i — индекс на елемент в A
- j — индекс на елемент в B
- k — индекс на първи свободен елемент в CАко i < m и j < n:
- избираме по-малкия елемент от A[i] и B[j]
- записваме го в C[k]
Иначе преминаваме към стъпка 4.Увеличаваме k с 1.
- Ако A[i] <= B[j], увеличаваме i с 1.
- Иначе увеличаваме j с 1.
- Повтаряме стъпка 2.Ако i < m, копираме останалите елементи от А[] в C[]
Иначе копираме останалите елементи от B[] в C[]
ПРИМЕР:
Нека сортираме следния масив (във възходящ ред):
Този пример ще бъде едно истинско приключение. 😅
Първата ни стъпка е да разделим масива на две части. Сигурно сте забелязали, че всъщност можем да прескочим тази част и направо да разделим масива на 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[]):
Когато елементите са по един, няма нужда да се задълбочаваме в това как работи алгоритъмът за сливане, а можем да го обобщим като:
- сравни елементите на 2-та подмасива и, ако не са във възходящ ред, ги размени
- обедини ги в един общ подмасив
Тъй като 14 < 33, няма да разменяме елементите, а направо ще ги обединим:
[14, 33], [27], [10], [35], [19], [42], [44]
Продължаваме със следващата двойка подмасиви, т.е. A = [ 27 ] и B = [ 10 ]:
Виждаме, че 27 > 10, затова разменяме елементите и след това ги обединяваме в един общ подмасив:
[14, 33], [10, 27], [35] , [19] , [42] , [44]
Продължаваме със следващата двойка подмасиви, т.е. A = [ 35 ] и B = [ 19 ]:
Виждаме, че 35 > 19, затова разменяме елементите и след това ги обединяваме в един общ подмасив:
[14, 33], [10, 27], [19, 35], [42], [44]
Продължаваме със следващата двойка подмасиви, т.е. A = [ 42 ] и B = [ 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 ]:
Сега вече ще вкараме алгоритъма за сливане в действие. 😅 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, така че след сливането, C = [ 10, 14, 27, 33 ].
Както виждаме, сляхме подмасивите в един общ сортиран подмасив. 😉 Ще следваме този принцип за сливане и по-нататък. Сега подмасивите ще изглеждат така:
[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 ]
Или, за да сме по-модерни, ще изглежда така 😅:
ИМПЛЕМЕНТАЦИЯ (Java):
—
Това е за днес! Ако видите някоя грешка — споделете, няма да ви се обидя! 😅
Top comments (0)