Сортиране при сливане: алгоритъм, предимства и функции

2024 Автор: Angel Austin | [email protected]. Последно модифициран: 2023-12-17 05:17

Merge sort е един от основните алгоритми за компютърни науки, формулиран през 1945 г. от великия математик Джон фон Нойман. Докато участва в проекта Манхатън, Нойман е изправен пред необходимостта да обработва ефективно огромни количества данни. Разработеният от него метод използва принципа „разделяй и владей“, което значително намалява времето, необходимо за работа.

Принцип и използване на алгоритъма

Методът за сортиране с обединяване се използва при проблеми на сортиране на структури, които имат подреден достъп до елементи, като масиви, списъци, потоци.

По време на обработка първоначалният блок с данни се разделя на малки компоненти, до един елемент, който всъщност вече е сортиран списък. След това се сглобява отново в правилния ред.

Сортирането на масив с определена дължина изисква допълнителна памет със същия размер, в която сортираният масив се събира на части.

Методът може да се използва за поръчка на всеки сравним тип данни, като например числа или низове.

Обединяване сортиранопарцели

За да разберем алгоритъма, нека започнем неговия анализ от края - от механизма на сливане на сортирани блокове.

Нека си представим, че имаме два масива от числа, сортирани по всякакъв начин, които трябва да бъдат комбинирани помежду си, за да не се наруши сортирането. За простота ще сортираме числата във възходящ ред.

Елементарен пример: и двата масива се състоят от по един елемент.


int arr1={31}; int arr2={18};


За да ги обедините, трябва да вземете нулевия елемент от първия масив (не забравяйте, че номерирането започва от нула) и нулевия елемент от втория масив. Това са съответно 31 и 18. Според условието за сортиране числото 18 трябва да е първо, тъй като е по-малко. Просто поставете числата в правилния ред:


int резултат={18, 31};


Нека разгледаме по-сложен пример, където всеки масив се състои от няколко елемента:


int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};


Алгоритъмът за сливане ще се състои от последователно сравняване на по-малки елементи и поставянето им в получения масив в правилния ред. За да следим текущите индекси, нека въведем две променливи - index1 и index2. Първоначално ги задаваме на нула, тъй като масивите са сортирани и най-малките елементи са в началото.


int index1=0; int index2=0;


Нека напишем целия процес на сливане стъпка по стъпка:

Вземете елемента с индекс1 от масива arr1 и елемента с индекс2 от масива arr2.
Сравнете, изберете най-малкия от тях и поставетеполучен масив.
Увеличете текущия индекс на по-малкия елемент с 1.
Продължете от първата стъпка.




Обединяване на подредени масиви

На първата орбита ситуацията ще изглежда така:


index1=0; индекс2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; индекс1++; резултат[0]=arr1[0]; // резултат=[2]


На втория завой:


index1=1; индекс2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; индекс2++; резултат[1]=arr2[0]; // резултат=[2, 5]


Трето:


index1=1; индекс2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; индекс2++; резултат[2]=arr2[1]; // резултат=[2, 5, 6]


И така нататък, докато резултатът е напълно сортиран масив: {2, 5, 6, 17, 21, 19, 30, 45}.
Могат да възникнат определени трудности, ако се обединят масиви с различни дължини. Ами ако един от текущите индекси достигне последния елемент и все още има останали членове във втория масив?


int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 стъпка index1=0, index2=0; 1 2 резултат={1, 2}; // 3 стъпка index1=1, index2=1; 4 < 5 резултат={1, 2, 4}; //4 стъпка index1=2, index2=1 ??


Променливата index1 е достигнала стойност 2, но масивът arr1 няма елемент с този индекс. Тук всичко е просто: просто прехвърлете останалите елементи от втория масив в получения, като запазите реда им.


резултат={1, 2, 4, 5, 6, 7, 9};


Тази ситуация ни показва нуждатасъпоставете текущия индекс за проверка с дължината на масива, който се обединява.
Схема за сливане за подредени последователности (A и B) с различни дължини:

Ако дължината на двете последователности е по-голяма от 0, сравнете A[0] и B[0] и преместете по-малката в буфера.
Ако дължината на една от последователностите е 0, вземете останалите елементи от втората последователност и без да променяте реда им, преминете към края на буфера.


Изпълнение на втория етап
По-долу е даден пример за свързване на два сортирани масива в Java.


int a1=new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=ново int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=ново int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } иначе if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }


Тук:

a1 и a2 са оригиналните сортирани масиви, които ще бъдат обединени;
a3 – краен масив;
i и j са индекси на текущи елементи за масиви a1 и a2.

Първото и второто ако условията гарантират, че индексите не надхвърлят размера на масива. Третият и четвъртият блок условия, съответно, се преместват в получения масив от по-малкия елемент.



Обединяване на низове за сортиране


Разделяй и владей
И така, научихме се да обединяваме сортиранитеколекции от ценности. Може да се каже, че втората част от алгоритъма за сортиране чрез сливане - самото сливане - вече е сортирана.
Въпреки това, вие все още трябва да разберете как да стигнете от оригиналния несортиран масив от числа до няколко сортирани, които могат да бъдат обединени.
Нека разгледаме първия етап от алгоритъма и да научим как да разделяме масиви.
Това не е трудно - оригиналният списък със стойности е разделен наполовина, след което всяка част също се раздвоява и така нататък, докато се получат много малки блокове.
Дължината на такива минимални елементи може да бъде равна на единица, тоест самите те могат да бъдат сортиран масив, но това не е необходимо условие. Размерът на блока се определя предварително и всеки подходящ алгоритъм за сортиране, който работи ефективно с масиви с малки размери (например бързо сортиране или сортиране с вмъкване), може да се използва за поръчката му.
Изглежда така.


// оригинален масив {34, 95, 10, 2, 102, 70}; // първо разделяне {34, 95, 10} и {2, 102, 70}; // второ разделяне {34} и {95, 10} и {2} и {102, 70}


Получените блокове, състоящи се от 1-2 елемента, са много лесни за подреждане.
След това трябва да обедините вече сортираните малки масиви по двойки, като запазите реда на членовете, което вече се научихме да правим.



Схема за сортиране на масив чрез обединяване


Изпълнение на първия етап
Рекурсивното разделяне на масив е показано по-долу.


void mergeSort(T a, дълъг старт, дълъг край) { long split; ако(старт < край) { split=(старт + край)/2; mergeSort(a, начало, разделяне); mergeSort(a, разделяне+1, край); сливане (а, начало, разделяне, край); } }


Какво се случва в този код:

Функцията mergeSort получава първоначалния масив
a
и лявата и дясната граница на региона за сортиране (индекси начало и
край).

Ако дължината на този раздел е по-голяма от една (
начало < край
), тогава той се разделя на две части (с индекс
split), и всеки от тях е рекурсивно сортиран.

При извикването на рекурсивна функция за лявата страна се предават началният индекс на графиката и индексът
split
. За десния съответно началото ще бъде
(разделяне + 1), а краят ще бъде последният индекс на оригиналния раздел.

Функция
merge
получава две подредени последователности (
a[start]…a[split]
и
a[разделяне +1]…a[завършване) и ги обединява в ред на сортиране.


Механиката на функцията за сливане е обсъдена по-горе.

Обща схема на алгоритъма
Методът на масива за сортиране при сливане се състои от две големи стъпки:

Разделете несортирания оригинален масив на малки парчета.
Съберете ги по двойки, като следвате правилото за сортиране.

Една голяма и сложна задача е разделена на много прости, които се решават последователно, което води до желания резултат.



Алгоритъм за сортиране при сливане


Оценка на метода
Времената сложност на сортирането със сливане се определя от височината на дървото за разделянеалгоритъм и е равен на броя на елементите в масива (n), умножен на неговия логаритъм (log n). Такава оценка се нарича логаритмична.
Това е едновременно предимство и недостатък на метода. Времето на работа не се променя дори в най-лошия случай, когато оригиналният масив е сортиран в обратен ред. Въпреки това, когато обработва напълно сортирани данни, алгоритъмът не осигурява печалба от време.
Важно е също да се отбележи цената на паметта на метода за сортиране чрез сливане. Те са равни на размера на оригиналната колекция. В тази допълнително разпределена зона се събира сортиран масив от парчетата.

Внедряване на алгоритъма
Паскал сортиране при сливане е показано по-долу.


Процедура MergeSort(име: низ; var f: текст); Var a1, a2, s, i, j, kol, tmp: цяло число; f1, f2: текст; b: булев Begincol:=0; Присвояване (f, име); нулиране (f); Въпреки че не EOF(f), започвайте да четете(f, a1); inc(col); край; затваряне (f); Assign(f1, '{име на 1-ви допълнителен файл}'); Assign(f2, '{име на 2-ри допълнителен файл}'); s:=1; Докато (s<kol) започва Reset(f); пренаписване (f1); пренаписване (f2); За i:=1 до kol div 2 започват Read(f, a1); Напишете (f1, a1, ' '); край; Ако (kol div 2) mod s0, тогава започнете tmp:=kol div 2; Докато tmp mod s0 започва Read(f, a1); Напишете (f1, a1, ' '); inc(tmp); край; край; Докато не EOF(f), започват Read(f, a2); Запис (f2, a2, ' '); край; затваряне (f); затваряне (f1); затваряне (f2); пренаписване (f); нулиране (f1); нулиране (f2); Четене (f1, a1); Четене (f2, a2); Докато (не EOF(f1)) и (не EOF(f2)) започват i:=0; j:=0; b:=вярно; Докато (b) и (не EOF(f1)) и (не EOF(f2)) започват, ако (a1<a2), тогава започватНапишете(f, a1, ' '); Четене (f1, a1); inc(i); End else begin Write(f, a2, ' '); Четене (f2, a2); inc(j); край; Ако (i=s) или (j=s), тогава b:=false; край; Ако не b, тогава започва While (i<s) и (не EOF(f1)) започва Write(f, a1, '); Четене (f1, a1); inc(i); край; Докато (j<s) и (не EOF(f2)) започват Write(f, a2, '); Четене (f2, a2); inc(j); край; край; край; Докато не EOF(f1) започва tmp:=a1; Четене (f1, a1); Ако не EOF(f1), тогава Write(f, tmp, ') иначе Write(f, tmp); край; Въпреки че не EOF(f2) започва tmp:=a2; Четене (f2, a2); Ако не EOF(f2), тогава Write(f, tmp, ') иначе Write(f, tmp); край; затваряне (f); затваряне (f1); затваряне (f2); s:=s2; край; Изтриване (f1); Изтриване (f2); Край;


Визуално работата на алгоритъма изглежда така (отгоре - неподредена последователност, отдолу - подредена).



Визуализация на сортиране при вмъкване


Сортиране на външни данни
Много често има нужда от сортиране на някои данни, намиращи се във външната памет на компютъра. В някои случаи те са с впечатляващ размер и не могат да бъдат поставени в RAM, за да се улесни достъпът до тях. За такива случаи се използват външни методи за сортиране.
Необходимостта от достъп до външни медии влошава ефективността на времето за обработка.
Сложността на работата е, че алгоритъмът може да има достъп само до един елемент от потока от данни в даден момент. И в този случай един от най-добрите резултати се показва от метода за сортиране с обединяване, който може да сравнява елементите на два файла последователно един след друг.
Четене на данни отвъншен източник, тяхната обработка и запис в крайния файл се извършват в подредени блокове (серии). Според начина на работа с размера на подредените серии има два вида сортиране: просто и естествено сливане.



Външно сортиране при сливане


Просто сливане
С просто сливане дължината на серията е фиксирана.
По този начин в оригиналния несортиран файл всички серии се състоят от един елемент. След първата стъпка размерът се увеличава до две. Следва - 4, 8, 16 и така нататък.
Работи така:

Изходният файл (f) е разделен на два спомагателни - f1, f2.
Те отново се обединяват в един файл (f), но в същото време всички елементи се сравняват по двойки и образуват двойки. Размерът на серията на тази стъпка става два.
Стъпка 1 се повтаря.
Стъпка 2 се повтаря, но вече подредените 2s се обединяват, за да образуват сортирани 4s.
Цикълът продължава, увеличавайки серията при всяка итерация, докато целият файл не бъде сортиран.

Как да разберете, че външното сортиране с просто сливане е завършено?

дължина на нова серия (след обединяване) не по-малко от общия брой елементи;
остава само един епизод;
Допълнителният файл f2 беше оставен празен.

Недостатъците на простото сливане са: тъй като продължителността на изпълнение е фиксирана при всеки проход на сливане, обработката на частично подредените данни ще отнеме толкова време, колкото и напълно произволните данни.

Естествен синтез
Този метод не ограничава дължинатасерия, но избира максимално възможния.
Алгоритъм за сортиране:

Четене на първоначалната последователност от файл f. Първият получен елемент се записва във файла f1.
Ако следващият запис отговаря на условието за сортиране, той се записва там, ако не, тогава във втория допълнителен файл f2.
По този начин се разпространяват всички записи на изходния файл и се формира подредена последователност във f1, която определя текущия размер на серията.
Файловете f1 и f2 са обединени.
Цикълът се повтаря.

Поради нефиксирания размер на поредицата е необходимо да се маркира краят на поредицата със специален знак. Следователно при сливане броят на сравненията се увеличава. Освен това размерът на един от помощните файлове може да е близък до размера на оригинала.
Средно естественото сливане е по-ефективно от обикновеното сливане с външно сортиране.

Характеристики на алгоритъма
При сравняване на две еднакви стойности методът запазва оригиналния им ред, тоест е стабилен.
Процесът на сортиране може да бъде много успешно разделен на множество нишки.



Image

Видеото ясно демонстрира работата на алгоритъма за сортиране при сливане.