Сортиране чрез сливане
В информатиката сортирането чрез сливане е алгоритъм за сортиране, базиран на сравняване, който винаги има сложност . Алгоритъмът се гради на принципа „разделяй и владей“. Създаден е от Джон фон Нойман през 1945. Стабилен е и паметта, която му трябва, в най-лошия случай е n. По-подробно описание и анализ на сортирането чрез сливане, се е появило в доклад на Goldstine и Neumann още през 1948 година.
Принцип на действие
редактиране- Несортираният списък по произволен начин се разделя на два подсписъка с приблизително еднаква дължина (за линейно време)
- Рекурсивно се разделят подсписъците, докато не се достигне до списъци с единична дължина
- Сливат се два подсписъка в нов сортиран списък (за линейно време)[1]
Примерен код на C#
редактиранеИма 2 метода. Първият разделя масива на 2, а втория сравнява елементите.
static int[] Splits(int[] arr)
{
if (arr.Length == 1) // Ако дължината на масива стане равна на 1 елемент,
{ // тогава се връща този елемент и отиваме към другия метод
return arr;
}
// Инициализират се два масива с равен брой елемента спрямо подаденият масив(arr).
int middle = arr.Length / 2;
int[] leftArr = new int[middle];
int[] rightArr = new int[arr.Length - middle];
// Слагаме в първия масив(left), половината от елементите на подадения масив (arr).
for (int i = 0; i < middle; i++)
{
leftArr[i] = arr[i];
}
// Слагаме във втория масив(right), другата половината от елементи на подадения масив (arr).
for (int i = middle, j = 0; i < arr.Length; i++, j++)
{
rightArr[j] = arr[i];
}
leftArr = Splits(leftArr); // Вика се рекурсия на лявата половина, докато нейната дължина не стане равна на 1.
rightArr = Splits(rightArr); // След като свършим изцяло с лявата половина на първоначално подадения масив,
// прави се същото и с дясната половина, докато не се изчерпят всички нейни стойности
return Merge(leftArr, rightArr); // Когато в двата масива остане само по 1 елемент, викаме метода
// Merge, който ще ги слее, разпределени по големина
}
Във втория метод ще трябват променливите leftIncrease и rightIncrease, за да се ходи по елементите на масивите.
static int[] Merge(int[] left, int[] right)
{
// Първоначално се сравнява нулевия елемент на левия масив с нулевия елемент на десния.
int leftIncrease = 0;
int rightIncrease = 0;
int[] arr = new int[left.Length + right.Length];
for (int i = 0; i < arr.Length; i++)
{
// Ако левият елемент е по-малък, той се записва в масива (arr) и се увеличава левия брояч (leftIncrease) с 1
// Ако всички елементи в десния масив свършат, то се прехвърлят автоматично останалите елементи в левия масив.
if (rightIncrease == right.Length || ((leftIncrease < left.Length) && (left[leftIncrease] <= right[rightIncrease])))
{
arr[i] = left[leftIncrease];
leftIncrease++;
}
else if (leftIncrease== left.Length || ((rightIncrease < right.Length)&&(left[leftIncrease] >= right[rightIncrease])))
{
arr[i] = right[rightIncrease];
rightIncrease++;
}
}
return arr;
}
Пример стъпка по стъпка
редактиранеПредимства и недостатъци
редактиранеПредимството на сортирането чрез сливане е, че винаги работи със сложност . Това е теоретически най-добрата алгоритмична сложност, която може да бъде постигната от универсален алгоритъм за сортиране. Недостатъкът му е, че допълнителната памет, която му трябва, е n. Тоест, ако имаме 1 милион елемента, то ще ни трябва памет за 2 милиона елемента, за да изпълним алгоритъма.
Паралелна обработка
редактиранеАлгоритъмът може да се използва паралелно, тоест на всяко едно ядро на процесора му се подава методът, който разделя масива на 2, и после се сливат числата наведнъж. Ако имаме 8 микропроцесора, на всеки процесор му се дава методът Split, и след това се съединяват наведнъж всичките 8 части. Алгоритъмът може да стане n пъти по-бърз, когато имаме n ядра.
Източници
редактиране- ↑ Наков, Преслав и др. Програмиране = ++Алгоритми; (Programming = ++Algorithms;). Пето преработено издание. София, Топтийм, 2015. ISBN 954-8905-06-X. с. 433. Посетен на 2023-05-08.