Сортиране чрез сливане

В информатиката сортирането чрез сливане е алгоритъм за сортиране, базиран на сравняване, който винаги има сложност . Алгоритъмът се гради на принципа „разделяй и владей“. Създаден е от Джон фон Нойман през 1945. Стабилен е и паметта, която му трябва, в най-лошия случай е n. По-подробно описание и анализ на сортирането чрез сливане, се е появило в доклад на Goldstine и Neumann още през 1948 година.

Анимация на сортиране чрез сливане. Елементите са представени като точки

Принцип на действие

редактиране
  1. Несортираният списък по произволен начин се разделя на два подсписъка с приблизително еднаква дължина (за линейно време)
  2. Рекурсивно се разделят подсписъците, докато не се достигне до списъци с единична дължина
  3. Сливат се два подсписъка в нов сортиран списък (за линейно време)[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 ядра.

Източници

редактиране
  1. Наков, Преслав и др. Програмиране = ++Алгоритми; (Programming = ++Algorithms;). Пето преработено издание. София, Топтийм, 2015. ISBN 954-8905-06-X. с. 433. Посетен на 2023-05-08.