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

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

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

Принцип на действие[редактиране | редактиране на кода]

  1. Несортирания списък по произволен начин се разделя на два подсписъка с приблизително обща дължина (за линейно време)
  2. Рекурсивно се разделят подсписъците, докато не се достигне до списъци с единична дължина
  3. Сливат се два подсписъка в нов сортиран списък (за линейно време)

Примерен код на 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 процесора.