Алгоритм злиття
Алгоритми злиття — це родина алгоритмів, які використовують декілька відсортованих списків (масивів) як вхідні дані та створюють єдиний вихідний список (масив), що містить усі елементи списків, розташовані у впорядкованому порядку. Ці алгоритми використовуються як підпрограми в різних алгоритмах сортування, найбільш відомі з них сортування злиттям.
Застосування
Алгоритм злиття відіграє важливу роль в алгоритмі сортування злиттям, алгоритмі сортування на основі порівняння. Концептуально алгоритм сортування злиттям складається з двох етапів:
- Рекурсивно розділяємо список на підсписки приблизно однакової довжини, до тих пір, доки кожен підсписок буде містити лише один елемент, або у випадку ітеративного (знизу вгору) сортування злиттям розглядається список з n елементів як n підсписків розміром 1(будь-який список довжини 1 можна вважати впорядкованим).
- Послідовно об'єднуємо підсписки, щоб створити новий впорядкований підсписок — на кожному кроці ми беремо менший з двох перших елементів підсписків і записуємо його в результуючий список. Лічильники номерів елементів результуючого списку і підсписку, з якого було взято елемент, збільшуємо на 1.
- Коли один з підсписків вичерпався, додаємо всі елементи, що залишилися з другого підсписку в результуючий список.
- Якщо результуючий список буде містити усі елементи — це впорядкований список.
Алгоритм злиття використовується неодноразово в алгоритмі сортування злиттям.
Приклад сортування злиття наведено на ілюстрації. Починається з невпорядкованого масиву з 7 цілих чисел. Масив розділений на 7 частин; кожна частина містить 1 елемент і впорядковується. Потім відсортовані частини об'єднуються для отримання більших, відсортованих частин, поки не залишиться 1, відсортований масив.
Алгоритм був винайдений Джоном фон Нейманом в 1945 році[1] під час роботи над «Манхеттенським проектом» як засіб обробки великих масивів статистичних даних.
Робота цих алгоритмів зазвичай займає час, пропорційну сумі довжин списків. Ці алгоритми також працюють з кількома рядками, помноженим на сумарну довжину, час від часу, щоб помістити індекс на найменший елемент, що може бути досягнуто за допомогою порядку пріоритету, який заснований на моменті часу O (log n), O (m log n) time, де n — кількість списків, які потрібно з'єднати, а m — сума довжин списків. Коли два списки довжиною m з'єднуються, нижня межа порівняння в гіршому випадку становить 2m — 1.
Об'єднання двох списків
Наведений нижче псевдокод демонструє алгоритм, який реалізує злиття вхідних списків (або пов'язані списки або масиви) А і В у новий список С[2][3]
first() — подає перший елемент списку;
append — додає елемент до списку;
rest() — подає список без першого елементу.
function merge(A,B)
var list C
while length(A) > 0 and length(B) > 0
if first(A) ≤ first(B)
append first(A) to C
A = rest(A)
else
append first(B) to C
right = rest(B)
end if
while length(A) > 0
append first(A) to C
A = rest(A)
while length(B) > 0
append first(B) to C
B = rest(B)
return C
Реалізація алгоритму мовою програмування С
Для роботи алгоритму ми повинні реалізувати наступні операції:
- Операцію для рекурсивного поділу масиву на групи (метод
Sort). - Злиття в правильному порядку (метод
Merge).
public void Sort(T[] items)
{
if (items.Length <= 1)
{
return;
}
int leftSize = items.Length / 2;
int rightSize = items.Length - leftSize;
T[] left = new T[leftSize];
T[] right = new T[rightSize];
Array.Copy(items, 0, left, 0, leftSize);
Array.Copy(items, leftSize, right, 0, rightSize);
Sort(left);
Sort(right);
Merge(items, left, right);
}
private void Merge(T[] items, T[] left, T[] right)
{
int leftIndex = 0;
int rightIndex = 0;
int targetIndex = 0;
int remaining = left.Length + right.Length;
while(remaining > 0)
{
if (leftIndex >= left.Length)
{
items[targetIndex] = right[rightIndex++];
}
else if (rightIndex >= right.Length)
{
items[targetIndex] = left[leftIndex++];
}
else if (left[leftIndex].CompareTo(right[rightIndex]) < 0)
{
items[targetIndex] = left[leftIndex++];
}
else
{
items[targetIndex] = right[rightIndex++];
}
targetIndex++;
remaining--;
}
}
Варто відзначити, що на відміну від лінійних алгоритмів сортування, сортування злиттям буде ділити і склеювати масив незалежно від того, був він відсортований спочатку чи ні. Тому, незважаючи на те, що в гіршому випадку він відпрацює швидше, ніж лінійний, в кращому випадку його продуктивність буде нижче, ніж у лінійного. Тому сортування злиттям — не найкраще рішення, коли треба впорядкувати частково впорядкований масив.
Паралельне злиття
У мультипрограмуванні масиви відсортованих значень можна ефективно об'єднати, використовуючи задачу пошуку всіх найближчих найменших значень.
Паралельне злиття також може бути реалізоване за допомогою алгоритму поділу за правилом. Цей алгоритм добре працює, коли використовується з швидким послідовним злиттям як базовий випадок для об'єднання малих масивів. Реалізація з використанням Intel Threading Building Blocks (TBB) та бібліотеки паралельних шаблонів Microsoft (PPL), яка працює з багатоядерними процесорами, добре зарекомендувала себе на практиці[4].
Підтримка в мовах програмування
Деякі мови програмування мають вбудовані або бібліотечні функції підтримки для об'єднання упорядкованих колекцій.
C++
Стандартна бібліотека C++ містить функцію std::merge, яка об'єднує два відсортовані масиви і std::inplace_mergeяка об'єднує два послідовно відсортованих масиви на місці . Клас std::listмає власний метод, merge()який приєднується до іншого списку. Типи підключених елементів повинні містити оператор менше (<) або повинен бути передбачений довільний компаратор.
C++ 17 дозволяє відрізняючись політики виконання, а саме послідовно, паралельно і паралельно-непослідовно[5].
Python
Стандартна бібліотека Python (станом на версію 2.6) також має функцію merge()в heapqмодулі, яка приймає кілька відсортованих масивів та об'єднує їх в один[6].
Переваги та недоліки
Переваги
- працює навіть на структурах даних послідовного доступу;
- добре поєднується з підкачкою та кешуванням пам'яті;
- непогано працює в паралельному варіанті: легко розбити завдання між процесорами порівну, але важко зробити так, щоб інші процесори взяли на себе роботу, в разі якщо один процесор затримається;
- не має «важких» вхідних даних;
- стійкий — зберігає порядок рівних елементів (що належать одному класу еквівалентності в порівнянні);
Недоліки
- на «майже відсортованих» масивах працює так само довго, як на хаотичних. Існує варіант сортування злиттям, який працює швидше на частково впорядкованих даних, але він вимагає додаткової пам'яті, в доповненні до тимчасового буферу, який використовується безпосередньо для сортування.
- вимагає додаткової пам'яті за розміром вихідного масиву.
Див. також
Джерела
- Donald Knuth . The Art of Computer Programming , Volume 3: Sorting and Searching , Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Pages 158—160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp. 197—207.
- Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1
- High Performance Implementation of Parallel and Serial Merge in C# with source in GitHub and in C++ GitHub
- Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). «Section 27.3: Multithreaded merge sort». Introduction to Algorithms (Third изд.). MIT Press and McGraw-Hill. стр. 797—804. ISBN 978-0-262-03384-8.
Примітки
- ↑ Knuth, Donald Ervin, 1938- (©1973-©1981). The art of computer programming. Reading, Mass.: Addison-Wesley Pub. Co. ISBN 0-201-03809-9. OCLC 823849.
- ↑ Mehlhorn, Kurt, 1949- (2008). Algorithms and data structures : the basic toolbox. Berlin: Springer. ISBN 978-3-540-77978-0. OCLC 272306813.
- ↑ Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). Practical in-place mergesort. 3 (1): Nordic J. Computing. с. 27—40.
- ↑ VJ Duvanenko, "Параллельный Merge", д - р Добба Journal, февраль 2011.
- ↑ "std:merge". cppreference.com. 2018-01-08. Retrieved 2018-04-28.
- ↑ 8.4. heapq — Heap queue algorithm — Python v2.7.5 documentation.