Сортировка Шелла на PHP | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
C++ Developer. Professional
-5%
Scala-разработчик
-8%
Backend-разработчик на PHP
-9%
Алгоритмы и структуры данных
-9%
Team Lead
-6%
Архитектура и шаблоны проектирования Golang Developer. Professional
-5%
HTML/CSS
-11%
C# ASP.NET Core разработчик
-5%
Kotlin Backend Developer
-8%
iOS Developer. Professional
-8%
Java Developer. Professional Web-разработчик на Python MS SQL Server Developer Android Developer. Basic Разработчик программных роботов (RPA) на базе UiPath и PIX Microservice Architecture Unity Game Developer. Basic Разработчик голосовых ассистентов и чат-ботов React.js Developer Node.js Developer Интенсив «Оптимизация в Java» Супер-практикум по использованию и настройке GIT Symfony Framework Java Developer. Basic Unity Game Developer. Professional Супер-интенсив Azure
Инфраструктура
Инфраструктурная платформа на основе Kubernetes
-6%
Экспресс-курс «IaC Ansible»
-10%
Administrator Linux.Basic
-10%
Мониторинг и логирование: Zabbix, Prometheus, ELK
-10%
Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes»
-30%
Administrator Linux. Professional
-6%
Экcпресс-курс «ELK»
-10%
Экспресс-курс по управлению миграциями (DBVC)
-10%
Базы данных Network engineer Cloud Solution Architecture Highload Architect Разработчик голосовых ассистентов и чат-ботов VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив "Tarantool"
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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

PHP_Deep_6.6_site-5020-03fa00.png

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

При сортировке мы сравниваем и сортируем элементы в массиве, отстоящие друг от друга на 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);

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

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

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться