Алгоритми злиття — це родина алгоритмів, які використовують декілька відсортованих списків (масивів) як вхідні дані та створюють єдиний вихідний список (масив), що містить усі елементи списків, розташовані у впорядкованому порядку. Ці алгоритми використовуються як підпрограми в різних алгоритмах сортування, найбільш відомі з них сортування злиттям.
Застосування
Алгоритм злиття відіграє важливу роль в алгоритмі сортування злиттям, алгоритмі сортування на основі порівняння. Концептуально алгоритм сортування злиттям складається з двох етапів:
- Рекурсивно розділяємо список на підсписки приблизно однакової довжини, до тих пір, доки кожен підсписок буде містити лише один елемент, або у випадку ітеративного (знизу вгору) сортування злиттям розглядається список з n елементів як n підсписків розміром 1(будь-який список довжини 1 можна вважати впорядкованим).
- Послідовно об'єднуємо підсписки, щоб створити новий впорядкований підсписок — на кожному кроці ми беремо менший з двох перших елементів підсписків і записуємо його в результуючий список. Лічильники номерів елементів результуючого списку і підсписку, з якого було взято елемент, збільшуємо на 1.
- Коли один з підсписків вичерпався, додаємо всі елементи, що залишилися з другого підсписку в результуючий список.
- Якщо результуючий список буде містити усі елементи — це впорядкований список.
Алгоритм злиття використовується неодноразово в алгоритмі сортування злиттям.
Приклад сортування злиття наведено на ілюстрації. Починається з невпорядкованого масиву з 7 цілих чисел. Масив розділений на 7 частин; кожна частина містить 1 елемент і впорядковується. Потім відсортовані частини об'єднуються для отримання більших, відсортованих частин, поки не залишиться 1, відсортований масив.
Алгоритм був винайдений Джоном фон Нейманом в 1945 році під час роботи над «Манхеттенським проектом» як засіб обробки великих масивів статистичних даних.
Робота цих алгоритмів зазвичай займає час, пропорційну сумі довжин списків. Ці алгоритми також працюють з кількома рядками, помноженим на сумарну довжину, час від часу, щоб помістити індекс на найменший елемент, що може бути досягнуто за допомогою порядку пріоритету, який заснований на моменті часу O (log n), O (m log n) time, де n — кількість списків, які потрібно з'єднати, а m — сума довжин списків. Коли два списки довжиною m з'єднуються, нижня межа порівняння в гіршому випадку становить 2m — 1.
Об'єднання двох списків
Наведений нижче псевдокод демонструє алгоритм, який реалізує злиття вхідних списків (або пов'язані списки або масиви) А і В у новий список С
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), яка працює з багатоядерними процесорами, добре зарекомендувала себе на практиці.
Підтримка в мовах програмування
Деякі мови програмування мають вбудовані або бібліотечні функції підтримки для об'єднання упорядкованих колекцій.
C++
Стандартна бібліотека C++ містить функцію std::merge
, яка об'єднує два відсортовані масиви, і std::inplace_merge
, яка об'єднує два послідовно відсортованих масиви на місці. Клас std::list
має власний метод merge()
, який приєднує до іншого списку. Типи підключених елементів повинні містити оператор менше (<), або ж повинен бути передбачений довільний компаратор.
C++ 17 дозволяє різні політики виконання, а саме послідовну, паралельну і паралельно-непослідовну.
Python
Стандартна бібліотека Python (станом на версію 2.6) також має функцію merge()
в heapq
модулі, яка приймає кілька відсортованих масивів та об'єднує їх в один.
Переваги та недоліки
Переваги
- працює навіть на структурах даних послідовного доступу;
- добре поєднується з підкачкою та кешуванням пам'яті;
- непогано працює в паралельному варіанті: легко розбити завдання між процесорами порівну, але важко зробити так, щоб інші процесори взяли на себе роботу, в разі якщо один процесор затримається;
- не має «важких» вхідних даних;
- стійкий — зберігає порядок рівних елементів (що належать одному класу еквівалентності в порівнянні);
Недоліки
- на «майже відсортованих» масивах працює так само довго, як на хаотичних. Існує варіант сортування злиттям, який працює швидше на частково впорядкованих даних, але він вимагає додаткової пам'яті, в доповненні до тимчасового буферу, який використовується безпосередньо для сортування.
- вимагає додаткової пам'яті за розміром вихідного масиву.
Див. також
Джерела
- Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.)
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 27.3 Багатопотокове сортування зливанням. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
- High Performance Implementation [ 13 листопада 2020 у Wayback Machine.] of Parallel and Serial Merge in C# with source in GitHub [ 19 листопада 2020 у Wayback Machine.] and in GitHub [ 28 листопада 2020 у Wayback Machine.]
Примітки
- Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — .(англ.)
- Mehlhorn, Kurt, 1949- (2008). Algorithms and data structures : the basic toolbox. Berlin: Springer. ISBN . OCLC 272306813.
- Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). Practical in-place mergesort. 3 (1): Nordic J. Computing. с. 27—40.
- . Архів оригіналу за 24 серпня 2011.
- . Архів оригіналу за 11 листопада 2020.
- . Архів оригіналу за 18 жовтня 2012.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritmi zlittya ce rodina algoritmiv yaki vikoristovuyut dekilka vidsortovanih spiskiv masiviv yak vhidni dani ta stvoryuyut yedinij vihidnij spisok masiv sho mistit usi elementi spiskiv roztashovani u vporyadkovanomu poryadku Ci algoritmi vikoristovuyutsya yak pidprogrami v riznih algoritmah sortuvannya najbilsh vidomi z nih sortuvannya zlittyam ZastosuvannyaSortuvannya zlittyam Algoritm zlittya vidigraye vazhlivu rol v algoritmi sortuvannya zlittyam algoritmi sortuvannya na osnovi porivnyannya Konceptualno algoritm sortuvannya zlittyam skladayetsya z dvoh etapiv Rekursivno rozdilyayemo spisok na pidspiski priblizno odnakovoyi dovzhini do tih pir doki kozhen pidspisok bude mistiti lishe odin element abo u vipadku iterativnogo znizu vgoru sortuvannya zlittyam rozglyadayetsya spisok z n elementiv yak n pidspiskiv rozmirom 1 bud yakij spisok dovzhini 1 mozhna vvazhati vporyadkovanim Poslidovno ob yednuyemo pidspiski shob stvoriti novij vporyadkovanij pidspisok na kozhnomu kroci mi beremo menshij z dvoh pershih elementiv pidspiskiv i zapisuyemo jogo v rezultuyuchij spisok Lichilniki nomeriv elementiv rezultuyuchogo spisku i pidspisku z yakogo bulo vzyato element zbilshuyemo na 1 Koli odin z pidspiskiv vicherpavsya dodayemo vsi elementi sho zalishilisya z drugogo pidspisku v rezultuyuchij spisok Yaksho rezultuyuchij spisok bude mistiti usi elementi ce vporyadkovanij spisok Algoritm zlittya vikoristovuyetsya neodnorazovo v algoritmi sortuvannya zlittyam Priklad sortuvannya zlittya navedeno na ilyustraciyi Pochinayetsya z nevporyadkovanogo masivu z 7 cilih chisel Masiv rozdilenij na 7 chastin kozhna chastina mistit 1 element i vporyadkovuyetsya Potim vidsortovani chastini ob yednuyutsya dlya otrimannya bilshih vidsortovanih chastin poki ne zalishitsya 1 vidsortovanij masiv Algoritm buv vinajdenij Dzhonom fon Nejmanom v 1945 roci pid chas roboti nad Manhettenskim proektom yak zasib obrobki velikih masiviv statistichnih danih Robota cih algoritmiv zazvichaj zajmaye chas proporcijnu sumi dovzhin spiskiv Ci algoritmi takozh pracyuyut z kilkoma ryadkami pomnozhenim na sumarnu dovzhinu chas vid chasu shob pomistiti indeks na najmenshij element sho mozhe buti dosyagnuto za dopomogoyu poryadku prioritetu yakij zasnovanij na momenti chasu O log n O m log n time de n kilkist spiskiv yaki potribno z yednati a m suma dovzhin spiskiv Koli dva spiski dovzhinoyu m z yednuyutsya nizhnya mezha porivnyannya v girshomu vipadku stanovit 2m 1 Ob yednannya dvoh spiskivNavedenij nizhche psevdokod demonstruye algoritm yakij realizuye zlittya vhidnih spiskiv abo pov yazani spiski abo masivi A i V u novij spisok S first podaye pershij element spisku append dodaye element do spisku rest podaye spisok bez pershogo elementu function merge A B var list C while length A gt 0 and length B gt 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 gt 0 append first A to C A rest A while length B gt 0 append first B to C B rest B return CRealizaciya algoritmu movoyu programuvannya SDlya roboti algoritmu mi povinni realizuvati nastupni operaciyi Operaciyu dlya rekursivnogo podilu masivu na grupi metod Sort Zlittya v pravilnomu poryadku metod Merge public void Sort T items if items Length lt 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 gt 0 if leftIndex gt left Length items targetIndex right rightIndex else if rightIndex gt right Length items targetIndex left leftIndex else if left leftIndex CompareTo right rightIndex lt 0 items targetIndex left leftIndex else items targetIndex right rightIndex targetIndex remaining Varto vidznachiti sho na vidminu vid linijnih algoritmiv sortuvannya sortuvannya zlittyam bude diliti i skleyuvati masiv nezalezhno vid togo buv vin vidsortovanij spochatku chi ni Tomu nezvazhayuchi na te sho v girshomu vipadku vin vidpracyuye shvidshe nizh linijnij v krashomu vipadku jogo produktivnist bude nizhche nizh u linijnogo Tomu sortuvannya zlittyam ne najkrashe rishennya koli treba vporyadkuvati chastkovo vporyadkovanij masiv Paralelne zlittyaU multiprogramuvanni masivi vidsortovanih znachen mozhna efektivno ob yednati vikoristovuyuchi zadachu poshuku vsih najblizhchih najmenshih znachen Paralelne zlittya takozh mozhe buti realizovane za dopomogoyu algoritmu podilu za pravilom Cej algoritm dobre pracyuye koli vikoristovuyetsya z shvidkim poslidovnim zlittyam yak bazovij vipadok dlya ob yednannya malih masiviv Realizaciya z vikoristannyam Intel Threading Building Blocks TBB ta biblioteki paralelnih shabloniv Microsoft PPL yaka pracyuye z bagatoyadernimi procesorami dobre zarekomenduvala sebe na praktici Pidtrimka v movah programuvannyaDeyaki movi programuvannya mayut vbudovani abo bibliotechni funkciyi pidtrimki dlya ob yednannya uporyadkovanih kolekcij C Standartna biblioteka C mistit funkciyu std merge yaka ob yednuye dva vidsortovani masivi i std inplace merge yaka ob yednuye dva poslidovno vidsortovanih masivi na misci Klas std listmaye vlasnij metod merge yakij priyednuye do inshogo spisku Tipi pidklyuchenih elementiv povinni mistiti operator menshe lt abo zh povinen buti peredbachenij dovilnij komparator C 17 dozvolyaye rizni politiki vikonannya a same poslidovnu paralelnu i paralelno neposlidovnu Python Standartna biblioteka Python stanom na versiyu 2 6 takozh maye funkciyu merge v heapqmoduli yaka prijmaye kilka vidsortovanih masiviv ta ob yednuye yih v odin Perevagi ta nedolikiPerevagi pracyuye navit na strukturah danih poslidovnogo dostupu dobre poyednuyetsya z pidkachkoyu ta keshuvannyam pam yati nepogano pracyuye v paralelnomu varianti legko rozbiti zavdannya mizh procesorami porivnu ale vazhko zrobiti tak shob inshi procesori vzyali na sebe robotu v razi yaksho odin procesor zatrimayetsya ne maye vazhkih vhidnih danih stijkij zberigaye poryadok rivnih elementiv sho nalezhat odnomu klasu ekvivalentnosti v porivnyanni Nedoliki na majzhe vidsortovanih masivah pracyuye tak samo dovgo yak na haotichnih Isnuye variant sortuvannya zlittyam yakij pracyuye shvidshe na chastkovo vporyadkovanih danih ale vin vimagaye dodatkovoyi pam yati v dopovnenni do timchasovogo buferu yakij vikoristovuyetsya bezposeredno dlya sortuvannya vimagaye dodatkovoyi pam yati za rozmirom vihidnogo masivu Div takozhAlgoritm sortuvannya Sortuvannya zlittyamDzherelaDonald Knut Sorting and Searching The Art of Computer Programming 3rd Massachusetts Addison Wesley 1998 T 3 780 s ISBN 0 201 89685 0 angl T Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 27 3 Bagatopotokove sortuvannya zlivannyam Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 High Performance Implementation 13 listopada 2020 u Wayback Machine of Parallel and Serial Merge in C with source in GitHub 19 listopada 2020 u Wayback Machine and in C GitHub 28 listopada 2020 u Wayback Machine PrimitkiDonald Knut Fundamental Algorithms The Art of Computer Programming 3rd Massachusetts Addison Wesley 1997 T 1 650 s ISBN 0 201 89683 4 angl 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 s 27 40 Arhiv originalu za 24 serpnya 2011 Arhiv originalu za 11 listopada 2020 Arhiv originalu za 18 zhovtnya 2012