Быстрая сортировка: реализация на PHP и JS | OTUS
⚡ Открываем подписку на курсы!
Проходите параллельно 3 онлайн-курса в месяц по цене одного.
Подробнее

Курсы

Программирование
Flutter Mobile Developer Подготовка к сертификации Oracle Java Programmer (OCAJP)
-8%
Алгоритмы и структуры данных
-12%
Web-разработчик на Python
-11%
Архитектура и шаблоны проектирования
-14%
JavaScript Developer. Basic Супер-интенсив «СУБД в высоконагруженных системах»
-18%
iOS-разработчик. Базовый курс
-23%
Разработчик на Spring Framework
-23%
Python Developer. Basic
-16%
C# ASP.NET Core разработчик
-18%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-6%
JavaScript Developer. Professional
-9%
Android Developer. Basic
-10%
Java Developer. Professional Разработчик C# AWS для разработчиков Highload Architect Reverse-Engineering. Professional CI/CD Vue.js разработчик Agile Project Manager Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Advanced Fullstack JavaScript developer
Инфраструктура
PostgreSQL
-10%
IoT-разработчик
-12%
Administrator Linux. Professional
-11%
Базы данных
-19%
Administrator Linux.Basic
-18%
Супер-интенсив «СУБД в высоконагруженных системах»
-18%
Супер-интенсив "SQL для анализа данных"
-16%
Software Architect
-12%
Сетевой инженер AWS для разработчиков Highload Architect Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Администратор Linux. Виртуализация и кластеризация Нереляционные базы данных Супер-практикум по использованию и настройке GIT
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Быстрая сортировка: реализация на PHP и JS

PHP_Deep_13.4-5020-0eb837.png

В этой статье поговорим о Быстрой сортировке (quicksort). Почему именно она? На мой взгляд, эта сортировка отлично подходит для решения повседневных задач. Ниже я приведу принцип данной сортировки и две её реализации — на PHP и JavaScript.

Wiki говорит, что быстрая сортировка была придумана английским информатиком Чарльзом Хоаром в 1960 году.

Сортировка работает следующим образом:

1) Выбирается опорный элемент. Его можно выбрать случайно, обозначить его последним или средним — это всё не будет влиять на эффективность.

2) Массив перестраивается следующим образом: слева от опорного алгоритма находятся элементы, которые меньше его или равны ему, справа — элементы, которые больше него.

На каждой итерации мы выполняем следующие действия а) выбираем два индекса low и high, равные крайнему левому и крайнему правому элементам входного массива; б) вычисляем индекс опорного элемента middle; в) увеличиваем low последовательно до тех пор, пока элемент с индексом low не будет больше или равен опорному; г) уменьшаем high последовательно до тех пор, пока элемент с индексом high не будет меньше или равен опорному; д1) если low = high, то мы нашли середину входного массива; д2) если low < high, то мы меняем эти элементы местами.

3) Далее мы начинаем рекурсивно упорядочивать полученные два массива из элементов, лежащих справа и слева от опорного элемента соответственно.

4) Рекурсивное обращение продолжается до тех пор, пока все входные наборы не будут содержать один или два элемента.

Данная сортировка — это глубокое улучшение сортировки «пузырьком». Она является одним из самых быстродействующих алгоритмов сортировки общего назначения.

От теории к практике

Рассмотрим реализацию на PHP. В функцию quickSort передаём три параметра: массив (по ссылке), левую границу и правую границу. Сразу же определяем $middle — опорный элемент. Мы возьмём в качестве него средний элемент массива. Далее начинаем два циклических обхода справа и слева до нахождения бОльшего и мЕньшего элементов относительно опорного, перебрасываем их. Затем рекурсивно вызываем quickSort для двух полученных массивов. Здесь всё достаточно просто, а код функции будет выглядеть вот так:

function quickSort(&$arr, $low, $high) {
        $i = $low;                
        $j = $high;
        $middle = $arr[ ( $low + $high ) / 2 ];  // middle — опорный элемент; в нашей реализации он находится посередине между low и high
        do {
            while($arr[$i] < $middle) ++$i;  // ищем элементы для правой части
            while($arr[$j] > $middle) $j;  // ищем элементы для левой части
            if($i <= $j){           
                // перебрасываем элементы
                $temp = $arr[$i];
                $arr[$i] = $arr[$j];
                $arr[$j] = $temp;
                // следующая итерация
                $i++; $j--;
            }
        } 
        while($i < $j);

        if($low < $j){
          // рекурсивно вызываем сортировку для левой части
          quickSort($arr, $low, $j);
        } 

        if($i < $high){
          // рекурсивно вызываем сортировку для правой части
          quickSort($arr, $i, $high);
        } 
    }

На JavaScript функция не будет сильно отличаться структурно, однако имеются некоторые моменты, касающиеся самого языка. В определении опорного элемента следует принудительно использовать округление, дабы не получить дробный индекс. Массив передается по ссылке по умолчанию, так что хитрить с приведением типов не следует.

function quickSort(arr, low, high) {
        var i = low;                
        var j = high;
        var middle = arr[ Math.round(( low + high ) / 2) ];  // middle — опорный элемент; в нашей реализации он находится посередине между low и high

        do {
            while(arr[i] < middle)
              {
                ++i;  // ищем элементы для правой части
              } 
            while(arr[j] > middle)
              {
                --j;  // ищем элементы для левой части
              }
            if(i <= j){           
                // перебрасываем элементы
                var temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                // следующая итерация
                i++; j--;
            }
        } 
        while(i < j);

        if(low < j){
          // рекурсивно вызываем сортировку для левой части
          quickSort(arr, low, j);
        } 

        if(i < high){
          // рекурсивно вызываем сортировку для правой части
          quickSort(arr, i, high);
        } 
    }

Рабочий пример сортировки можно посмотреть тут.

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

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

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

Автор
1 комментарий
0

Добрый день! Опять попахивает google translate. "Его можно выбрать случайно, обозначить его последним или средним — это всё не будет влиять на эффективность." - найдите мне нашего соотечественника, который говорит: обозначьте мне, пожалуйста, этот элемент средним! "Выбирается опорный элемент. Его можно выбрать случайно, обозначить его последним или средним — это всё не будет влиять на эффективность." - это утверждение, насколько я понимаю, некорректно или некорректно сформулировано. Рандомизированный QuickSort в отличие от обычного имеет worst case O(N log N) см, например, https://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf Не лучшим образом описан сам алгоритм: "На каждой итерации мы выполняем следующие действия" - какие итерации? откуда взялись эти итерации? не совсем понятно, где конец каждой итерации и сколько их всего. Много вопросов к описанию алгоритма. Хорошо, что здесь не Хабр. Но предлагаю все же устроить небольшой филиал Хабра. "вычисляем индекс опорного элемента middle;" - как вычисляем? "два индекса low и high, равные крайнему левому и крайнему правому элементам входного массива;" - "индексы" не могут быть равны "элементам" - некорректная формулировка. После п. "д2" имеется какая-то лакуна, потому что в программе мы видим инкремент и декремент счетчиков, а описание про это тактично умалчивает. "Данная сортировка — это глубокое улучшение сортировки «пузырьком»." - очень сомнительно и бездоказательно. Что конкретно имеется в виду? "Рекурсивное обращение продолжается до тех пор..." - не по-русски. Вопросов много, но уже читать можно по сравнению со статьями, которые я видел раньше. Будем работать над улучшением статей вместе! На Хабре, кстати, явно помечают перевод "переводом" и тут же дают ссылку на оригинал. "Чтобы страна знала своих героев".

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