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

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

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

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

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

Примерен код на C#[редактиране | edit source]

Има 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;
    }

Пример стъпка по стъпка[редактиране | edit source]

Пример, как сортирането чрез сливане сортира една редица.

Предимства и недостатъци[редактиране | edit source]

Предимството на сортирането чрез сливане е, че винаги работи със сложност n*log(n). Това е теоретически най-добрата алгоритмична сложност, която може да бъде постигната от универсален алгоритъм за сортиране. Недостатъкът му е, че паметта, която му трябва, е n. Тоест ако имаме 1 милион елемента, то ще ни трябва памет за 2 милиона елемента, за да изпълним алгоритъма.

Паралелна обработка[редактиране | edit source]

Алгоритъмът може да се използва паралелно, тоест на всяко едно ядро на процесора му се подава методът, който разделя масива на 2, и после се сливат числата наведнъж. Ако имаме 8 микропроцесора, на всеки процесор му се дава методът Split, и след това се съединяват наведнъж всичките 8 части. Алгоритъмът може да стане n пъти по-бърз, когато имаме n процесора.