Відкрити головне меню
Приклад сортування злиттям

Сортування злиттям (англ. merge sort) — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй».

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так доти, доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме доти, доки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

Алгоритм сортуванняРедагувати

Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] – впорядкована ділянка довжини r. Наприклад,

Y 1 3 13 2 4 88
m m+1 m+s-1 m+s m+s+1 m+s+r

Результатом злиття повинна бути ділянка довжини r+s у масиві X:

X 1 2 3 4 13 88
m m+1 m+2 m+3 m+s+r

Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], … , A[n] копіюються в допоміжний масив B[1], … , B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1. На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t=nmod4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t. Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n. Розглянемо сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n=11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";": < <11><10> ; <9><8> ; <7><6> ; <5><4> ; <3><2> ; <1> >, lp=1 < <10, 11><8, 9> ; <6, 7><4, 5> ; <2, 3><1> >, lp=2 < <8, 9, 10, 11><4, 5, 6, 7>;<1, 2, 3> >, lp=4 < <4, 5, 6, 7, 8, 9, 10, 11><1, 2, 3> >, lp=8 <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp=16, lp³ n. Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив. Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1<n, то при виконанні останнього кроку мають місце співвідношення lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp, і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив. Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+ëlog2nû =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn). Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+ë log2nû ) та округлене відношення r двох останніх:

n n(n-1)/2 n(1+ë log2nû ) r
10 45 40 1
100 4950 700 7
1000 499500 10000 50
10000 49995000 140000 350

Як бачимо, кожне зростання n у 10 разів веде до зростання n(n-1)/2 та n(1+ë log2nû ) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове! Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … – злиття в протилежному напрямку. Переробка алгоритму залишається вправою. Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний: Ця функція набагато коротше нерекурсивної функції, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції". Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.

Псевдокод алгоритмуРедагувати

Процедура   здійснює часткове впорядкування масиву  , впорядковуючи його елементи з p-го по q-ий   здійснить впорядкування всього масиву).

 
1 if  
2    then return
3    
4 if  
5     
6     
7  

  використовує допоміжну процедуру  , що здійснює об'єднання частин масиву A з p-го по c-ий елемент і з c+1-го по q-ий елемент в один впорядкований підмасив. Для цього використовується один додатковий масив   такої ж довжини як і   (В деяких реалізаціях   вдвічі коротший за   — мінімально можлива його довжина).

 
1  
2  
3 for   to  
4     do if   або (  і  )
5           then  
6                 
7           else  
8                 
9 for   to  
10    do  

Аналіз алгоритмуРедагувати

Час роботи алгоритму   по впорядкуванню   елементів задовільняє рекурентному співвідношенню:

 , де   — час на впорядкування половини масиву,   — час на злиття цих половинок.

Враховуючи, що  , розв'язком співвідношення є  .

Крім того, алгоритм потребує для своєї роботи   додаткової пам'яті.

Алгоритм не міняє порядок розташування однакових елементів, а отже він є стабільним.

Можливі оптимізаціїРедагувати

Швидкість алгоритму є асимптотично оптимальною. Але її можна пришвидшити в константну кількість разів.

  • Оптимізація впорядкування невеликих частин масиву — невеликі частини масиву (наприклад, при q-p<50) впорядковувати сортуванням вставкою.
  • Оптимізація кількості копіювань елементів — при злитті двох впорядкованих масивів в один, кожен елемент копіюється два рази (спочатку у тимчасовий масив, а потім знову у початковий). Кількість копіювань можна зменшити удвічі, якщо по черзі використовувати для об'єднання початковий і тимчасовий масиви. Тоді можна не виконувати зайві операції копіювання (рядки 9-10 процедури Merge).

Робота алгоритмуРедагувати

Схема алгоритму для конкретного прикладу послідовності

Проілюструємо алгоритм сортування на такій послідовності: 42 5 30 36 25 10 37 49 0 0 На початку сортування відсортовані підпослідовності містять в собі по одному елементу.

Крок 1: 5 42 | 30 36 | 10 25 | 37 49 | 0 0

Крок 2: 5 30 36 42 | 10 25 37 49 | 0 0

Крок 3: 5 10 25 30 36 37 42 49 | 0 0

Крок 4: 0 0 5 10 25 30 36 37 42 49

Тестування алгоритмуРедагувати

Для перевірки правильності сортування звіримо сортування проведене програмою з сортуванням за даним алгоритмом вручну.

Проведемо сортування наступної послідовності: 56 19 3 95 23 17 38 44 69 73 84

На початку сортування послідовність є розбита на відсортовані підпослідовності по одному елементу в кожній.

56 | 19 | 3 | 95 | 23 | 17 | 38 | 44 | 69 | 73 | 84

далі кожні дві підпослідовності зливаються в одну відсортовану підпослідовність : 19 56 | 3 95 | 17 23 | 38 44 | 69 73 | 84

на наступному кроці отримаємо наступний результат злиття: 3 19 56 95 | 17 23 38 44 | 69 73 84 |

потім: 3 17 19 23 38 44 56 95 | 69 73 84 |

на останньому кроці отримаємо відсортовану послідовність: 3 17 19 23 38 44 56 69 73 84 | 95

Послідовність була відсортована за 4 кроки.

Приклад реалізації на С++Редагувати

#include <algorithm>
#include <vector>
using namespace std;

template <typename T>
void merge_sort(T* elems, //original array
                T* tmp_elems, //temp array to hold intermediate results, should be same size as array "elems"
                size_t size)
{
    if (size <= 1) {return;} //nothing to sort
    
    const size_t left_size = size / 2;
    const size_t right_size = size - left_size;
    
    merge_sort(elems, tmp_elems, left_size);
    merge_sort(elems + left_size, tmp_elems + left_size, right_size);
    
    T* leftIt = elems; // pointer to walk through left part
    T* const pivot = elems + left_size; //end of left part, start of right  part
    T* rightIt = pivot; // pointer to walk through right part
    T*const end = elems + size;
    T* outputIt = tmp_elems; //pointer to where to write when merging left and right subparts
    
    while (true)
    {
        if (*leftIt < *rightIt)
        {
            *outputIt++ = *leftIt++;
            if (leftIt == pivot)
            {
                // copy the rest of right part that has not been copied yet
                copy(rightIt,
                     end,
                     outputIt);
                break;
            }
        }
        else
        {
            *outputIt++ = *rightIt++;
            if (rightIt == end)
            {
                // copy the rest of left part that has not been copied yet
                copy(leftIt,
                     pivot,
                     outputIt);
                break;
            }
        }
    }
    
    copy(tmp_elems,
         tmp_elems + size,
         elems);
}

Алгоритм об'єднання без додаткової пам'ятіРедагувати

Цей алгоритм впорядкування масиву є модифікацією сортування злиттям. Він також є стабільним, але не потребує додаткової пам'яті.

Псевдокод алгоритмуРедагувати

Процедура   працює аналогічно процедурі   сортування злиттям:

 
1 if  
2    then return
3    
4  
5  
6  

Відмінність алгоритмів полягає в процедурі  , яка здійснює об'єднання двох впорядкованих масивів без додаткової пам'яті, але за час  .

Існує декілька алгоритмів об'єднання двох впорядкованних масивів, що не потребують додаткової пам'яті. Розглянемо лише один з них.

Ідея алгоритму злиттяРедагувати

Нехай алгоритм має об'єднати дві частини масиву   — з  -го по  -ий і з  -го по  -ий.

Виконаємо об'єднання в декілька етапів:

1. Знайдемо такі індекси  , що  
 
2. Змінимо порядок елементів масиву з   на
 
3. Викличемо рекурсивне злиття для половин нового масиву.

Тобто, спочатку ми знаходимо елементи, що мають лежати в першій половині масиву (найменші), потім переміщаємо найменші елементи в цю половину. Тоді можна окремо впорядкувати першу і другу половини масива (кожна з половин також буде складатися з двох впорядкованних частин, що треба об'єднати).

Пункт 1, можна виконати за один лінійний прохід. Другий крок — це по-суті циклічний зсув частини масиву на j елементів. Він може бути виконаний за лінійний час, наприклад, за допомогою трьох перегортань.

Псевдокод алгоритму злиттяРедагувати

 
1. if   або  
2.    then return
3.  
4.  
5.  
6.  
7. While   
8. do    if  
9.       then  
10.      else  
11.       
12.  
13.  
14.  
15.  
16.  

Функція   перегортає або дзеркально відображає частину масиву A з a-го по b-ий елементи включно.

Аналіз алгоритмуРедагувати

Спочатку проаналізуймо функцію ModifiedMerge. Вона виконує два кроки, що потребують O(n) часу, і двічі викликає себе від масиву, що у двічі менший за початковий.

Отже, час роботи функції на масиви довжиною n:  

Тепер можемо визначити час роботи алгоритму впорядкування, він виражається рівнянням:

 

ЗастосуванняРедагувати

Алгоритм використовується в деяких реалізаціях функції stable_sort() з стандартної бібліотеки шаблонів (STL) мови програмування C++.


ДжерелаРедагувати

  • Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1

ПосиланняРедагувати