|
Алгоритм злиттяАлгоритми злиття — це родина алгоритмів, які використовують декілька відсортованих списків (масивів) як вхідні дані та створюють єдиний вихідний список (масив), що містить усі елементи списків, розташовані у впорядкованому порядку. Ці алгоритми використовуються як підпрограми в різних алгоритмах сортування, найбільш відомі з них сортування злиттям. Застосування Алгоритм злиття відіграє важливу роль в алгоритмі сортування злиттям, алгоритмі сортування на основі порівняння. Концептуально алгоритм сортування злиттям складається з двох етапів:
Алгоритм злиття використовується неодноразово в алгоритмі сортування злиттям. Приклад сортування злиття наведено на ілюстрації. Починається з невпорядкованого масиву з 7 цілих чисел. Масив розділений на 7 частин; кожна частина містить 1 елемент і впорядковується. Потім відсортовані частини об'єднуються для отримання більших, відсортованих частин, поки не залишиться 1, відсортований масив. Алгоритм був винайдений Джоном фон Нейманом в 1945 році[1] під час роботи над «Манхеттенським проектом» як засіб обробки великих масивів статистичних даних. Робота цих алгоритмів зазвичай займає час, пропорційну сумі довжин списків. Ці алгоритми також працюють з кількома рядками, помноженим на сумарну довжину, час від часу, щоб помістити індекс на найменший елемент, що може бути досягнуто за допомогою порядку пріоритету, який заснований на моменті часу O (log n), O (m log n) time, де n — кількість списків, які потрібно з'єднати, а m — сума довжин списків. Коли два списки довжиною m з'єднуються, нижня межа порівняння в гіршому випадку становить 2m — 1. Об'єднання двох списківНаведений нижче псевдокод демонструє алгоритм, який реалізує злиття вхідних списків (або пов'язані списки або масиви) А і В у новий список С[2][3]
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
Реалізація алгоритму мовою програмування СДля роботи алгоритму ми повинні реалізувати наступні операції:
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++ містить функцію C++ 17 дозволяє різні політики виконання, а саме послідовну, паралельну і паралельно-непослідовну[5]. PythonСтандартна бібліотека Python (станом на версію 2.6) також має функцію Переваги та недолікиПереваги
Недоліки
Див. такожДжерела
Примітки
|