Сортировка слиянием на PHP

Сортировка слиянием это один из простых быстрых алгоритмов сортировки.
Именно среди быстрых, но на фоне скажем сортировки выбором или вставкой он будет более сложным и громоздким.

Сортировка слиянием построена на концепции "разделяй и властвуй".
Концепция в общем то проста по сути своей и сводится к тому, что общую большую задачу надо делить на более мелкие под задачи, а итоговый результат всех мелких подзадач сливать в одно место получая итоговый результат.

Сразу отмечу, что так как алгоритм все таки не самый маленький, и как правило состоит из двух функций, одна из них которая рекурсивная, то есть множество реализаций сортировки слиянием.
Как правило каждая реализация стремиться, что то улучшить и оптимизировать, сделать либо алгоритм в целом более быстрым, либо сделать его более быстрым для сортировки конкретных данных.

Сегодня мы посмотрим на две реализации, но по сути они будут одинаковы, разница заключается лишь в том, что в первой будет реализована процедура, а во втором функция в первичном ее понимании.

Я уточню:
1) Под процедурой я понимаю функцию, которая ничего не возвращает, а работает сама в себе и меняет по факту переданные в нее данные.
2) Функция в первичном своем понимании обязательно должна возвращать какой то результат. В нашем случае это будет отсортированный массив.

Так же поймем почему первый вариант более предпочтительный.

Сразу отмечу, что временная сложность алгоритма тета от n lg n.
То есть среднее время работы при любых входных данных будет довольно быстрым, особенно если посмотреть на сложность алгоритма вставками, которая составляет n^2.
К минусам данной сортировки стоит отнести повышенное потребление памяти и большое количество константных операций. Но в прочем и первое и второе поддается оптимизации.

Итак, для начала не много общей теории работы сортировки слиянием.
Как вы думаете, какой массив отсортирован по умолчанию? Правильно, массив из одного элемента. Наша задача сводится к тому, что бы раздробить исходный массив на минимальные элементы (минимальный элемент тут либо массив из одного значения, либо массив из пары значений, зависит от подхода).

После чего мы производим слияние этих минимальных элементов в кусочки побольше, после чего уже сливаем кусочки побольше в еще большие, пока у нас не сформируется отсортированный массив.

Под слиянием имеется ввиду именно сама сортировка, и делается она за линейное время, так как входные подмассивы уже отсортированы (начиная с массива в один элемент).

Более подробно про само слияние.
Когда у нас два подмассива, которые уже отсортированы отсортировать их в один массив можно довольно быстро, достаточно сверять первые элементы и заносить их в новый массив.

    Например у нас есть два массива A и B с элементами:
  • 1) A 1, 3, 4
  • 2) B 2, 5, 7

Что бы слить их в один отсортированный массив N, мы сначала сверяем 1 и 2, заносим 1 в массив N(1), потом сверяем 3 и 2, добавляем к единице двойку N(1,2), потом 3 и 5 N(1,2,3) и так далее пока не кончится один из массивов, после чего остаток другого массивы мы заносим в конец N.

Теперь посмотрим на алгоритм в целом.
Скажем на вход у нас дается массив A из четырех элементов A(4, 0, 3, 2).
Мы разбиваем этот массив пополам и получаем два подмассива:
1) A1(4, 0)
2) A2(3,2)

После этого мы еще раз разбиваем массив A1 на два подмассива получая массивы по одному значению A11(1) и A12(4), которые отсортированы по умолчанию.

Далее мы производим слияние массивов A11 иA12, Получая на выходе отсортированный массив A1(0, 4).

После чего мы беремся за вторую половину массива A. Точно так же разбиваем A2 на два подмассива 3 и 2, производим слияние и получаем A2(2,3).

И наконец после этого мы производим слияние двух половинок массива A.
A1(0, 4) и A2(2,3) -> A(0,2,3,4).

Теперь посмотрим на настоящий код:

function mergeSort(&$mas, $s, $f)
{    
    if($s < $f)
    {
        $q = (int) (($s+$f)/2);
        
        mergeSort($mas, $s, $q);
        mergeSort($mas, $q+1, $f);
        
        merge($mas, $s, $q, $f);
    }
}

Это рекурсивная функция, которая дробит основной массив на более мелкие части, именно в этом случае вплоть до пары элементов.

На вход у нас идет сортируемый массив. Обратите внимание, что перед $mas стоит символ &, это означает, что массив передается по ссылке, то есть работа идет непосредственно в передаваемом массиве.
Иначе этого можно достичь сделав $mas глобальной переменной, но это будет менее гибко.

S - переменная которая хранит индекс начала рассматриваемого подмассива в контексте массива mas.

F - хранит индекс конца рассматриваемого подмассива.

Далее if($s < $f) проверка на то не достигли ли мы едничиного массива.
В качестве минимального массива в функции mergeSort нам нужен массив из пары элементов (дальнейшее его разбиение на массивы по одному элемент будет в функции merge). Одновременно это условие является выходом из рекурсии.

Итак, если у нас массив состоит минимум из двух элементов, мы проходим дальше и ищем середину этого массива q = (int) (($s+$f)/2).

После чего рекурсивно вызываем сами себя для двух половинок массива, от начала s до середины q и от середины q до конца f.

Когда же достигнут предел рекурсии происходит передача управления функции выше и вызывается функция merge.

function merge(&$mas, $s, $q, $f)
{
    for($i=$s; $i<=$q; $i++)
    {
        $subMasLeft[] = $mas[$i];
    }
    
    for($i=$q+1; $i<=$f; $i++)
    {
        $subMasRight[] = $mas[$i];
    }
    
    $subMasLeft[] = INF;
    $subMasRight[] = INF;
    
    $l = 0;
    $r = 0;
    
    for($i=$s; $i<=$f; $i++)
    {
        if($subMasLeft[$l] <= $subMasRight[$r])
        {
            $mas[$i] = $subMasLeft[$l];
            $l++;
        }
        else
        {
            $mas[$i] = $subMasRight[$r];
            $r++;
        }
    }
}

Она не рекурсивна и ее задача состоит в сортировке двух подмассивов. Опять же обратите внимание, что происходит передача параметра mas по ссылке, что позволяет нам работать с сортируемым массивом напрямую.

В качестве подмассивов у нас выступают интервалы массива mes. То есть A[s...q] и B[q+1...f].

Первым делом мы сразу формируем два реальных подмассива из заданных интервалов, именно поэтому в сортировке слиянием повышенное потребление памяти.
У нас получаются два массива subMasLeft - подмассив слева от середины, и массив subMasRight справа от середины. При первой итерации выполнения это будут массивы из одного значения.
Массивы уже отсортированы и нам надо провести слияние.

Далее идет добавление в конец каждого массива бесконечно большого значения, это небольшая уловка, которая позволит нам избежать лишних конструкций в цикле слияния. То есть когда мы дойдем до конца одного из массивов, то значения из второго массива будут сравниваться с бесконечно большим числом.

Если обходится без этой уловки, то придется в цикле проверять не достигли ли мы конца массива, а если достигли, то придется еще делать цикл на копирование оставшихся элементов.

Так же у нас вводятся две переменные l и r, которые будут курсорами индекса для массивов subMasLeft и subMasRight.

Заметьте, что цикл идет от s до f, то есть по большому интервалу основного массива mas, что позволяет перезаписывать его элементы в упорядоченном виде.

В цикле мы просто проверяем последовательно элементы массивов и наименьший записываем в mas, увеличивая счетчик l и r.

    Вот собственно и все, во время сортировки в массиве mas будут происходит перестановки.
    Выглядеть это будет так A(1, 4, 3, 7, 5, 0):
  • 1) 1, 4, 3, 7, 5, 0 - 1 и 4
  • 3) 1, 3, 4, 7, 5, 0 - 1,4 и 3
  • 4) 1, 3, 4, 5, 7, 0 - 7 и 5
  • 5) 1, 3, 4, 0, 5, 7 - 5,7 и 0
  • 6) 0, 1, 3, 4, 5, 7 - 0,1,3 и 4,5,7

Теперь покажу код функционального подхода

function mergeSort($mas)
{    
    if(count($mas) <= 1)
    {
    return $mas;
    }
    else
    {
    $q = (int) (count($mas)/2);
    return merge(mergeSort(array_slice($mas, 0, $q)), mergeSort(array_slice($mas, $q)));
    }
}

Главное его отличие в том, что работа ведется с внтренней копией массива mas, а функция mergeSort возвращает значения при каждом выполнении.
На мой взгляд этот код более явно показывает парадигму "разделяй и властвуй".

mergeSort делит массив mas до единичным массивов, а потом начинает работать функция merge, которая сливает все кусочки.

Функция merge тоже не много поменяется

function merge($leftMas, $rightMas)
{    
    $twoMasCount = count($leftMas)+count($rightMas);
    
    $leftMas[] = INF;
    $rightMas[] = INF;
    
    $l = 0;
    $r = 0;
    
    for($i=0; $i<$twoMasCount; $i++)
    {
        if($leftMas[$l] <= $rightMas[$r])
        {
            $mas[] = $leftMas[$l];
            $l++;
        }
        else
        {
            $mas[] = $rightMas[$r];
            $r++;
        }
    }
    
    return $mas;
}

На вход у нас принимаются уже существующие подмассивы, а копирование результирующего массива происходит в буфер mas, который возвращается merge.

Мои опыты показали, что процедурный подход работает на 15% быстрее.
При этом он потребляет на 40% меньше памяти.


comments powered by Disqus