Сортировка Шелла на PHP

Эту статью я бы хотел посвятить замечательному алгоритму сортировки, носящему имя Дональда Шелла. Не секрет, что сортировка Шелла зачастую работает медленнее, чем быстрая сортировка (сортировка Хоара), которую мы рассматривали здесь. Однако, быстрая сортировка быстро замедляется до квадратичной сложности при неудачном наборе данных, что является худшим результатом, чем худшее время для сортировки Шелла.

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

Особое внимание нужно уделить выбору набора расстояний n. Сам Дональд Шелл предложил последовательность N1 = L/2, Ni = Ni-1/2, Nk = 1. Такая последовательность в худшем случае обеспечивает квадратичную сложность.

Улучшение этой последовательности разработал Роберт Седжвик (кстати, автор отличной книжки по алгоритмам): Ni = 92^i — 92^(i/2) + 1. При этом требуется остановка на значении inc[s-1], если 3*inc[s] > size, где size — размер сортируемого массива. В худшем случае сложность будет порядка 4/3.

Для массивов до 4000 элементов лучшей считается последовательность Циура: {1, 4, 10, 23, 57, 132, 301, 701, 1750}.

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

function(&$a){
    $sort_length = count($a) - 1;
    $step = ceil(($sort_length + 1)/2);

    do{
        // тело цикла

        // конец цикла
        $step = $step / 2;
    }
    while($step > 0)
}

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

    // тело цикла

    $i = ceil($step);
       do
       {
         $j=$i-$step;
         $c=1;
         do
         {
           if($a[$j]<=$a[$j+$step])
           {
            $c=0;
           }
           else
           {
              $tmp=$a[$j];
              $a[$j]=$a[$j+$step];
              $a[$j+$step]=$tmp;
           }
        $j=$j-1;
         }
         while($j>=0 && ($c==1));
          $i = $i+1;
        }
        while($i<=$sort_length);

        // конец цикла

Вот и всё. Подробности и результат сортировки смотрите в моём гитхабе.