Сортировка Шелла на PHP | OTUS
🔥 Начинаем BLACK FRIDAY!
Максимальная скидка -25% на всё. Успейте начать обучение по самой выгодной цене.
Выбрать курс

Курсы

Программирование
iOS Developer. Basic
-25%
Python Developer. Professional
-25%
Разработчик на Spring Framework
-25%
Golang Developer. Professional
-25%
Python Developer. Basic
-25%
iOS Developer. Professional
-25%
Highload Architect
-25%
JavaScript Developer. Basic
-25%
Kotlin Backend Developer
-25%
JavaScript Developer. Professional
-25%
Android Developer. Basic
-25%
Unity Game Developer. Basic
-25%
Разработчик C#
-25%
Программист С Web-разработчик на Python Алгоритмы и структуры данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Vue.js разработчик VOIP инженер Программист 1С Flutter Mobile Developer Супер - интенсив по Kubernetes Symfony Framework Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-25%
DevOps практики и инструменты
-25%
Архитектор сетей
-25%
Инфраструктурная платформа на основе Kubernetes
-25%
Супер-интенсив «ELK»
-16%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив "SQL для анализа данных"
-16%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Администратор Linux. Виртуализация и кластеризация Нереляционные базы данных Супер-практикум по использованию и настройке GIT IoT-разработчик Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться
🎁 Максимальная скидка!
Черная пятница уже в OTUS! Скидка -25% на всё!