Быстрая сортировка: реализация на PHP и JS | OTUS
Черная пятница уже наступила!
Все курсы ноября со скидкой 30%. Торопитесь!
Подробнее

Курсы

Курсы в разработке Подготовительные курсы
Работа в компаниях Компаниям Блог +7 499 110-61-65

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

PHP_Deep_6.5_site-5020-aebc88.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" имеется какая-то лакуна, потому что в программе мы видим инкремент и декремент счетчиков, а описание про это тактично умалчивает. "Данная сортировка — это глубокое улучшение сортировки «пузырьком»." - очень сомнительно и бездоказательно. Что конкретно имеется в виду? "Рекурсивное обращение продолжается до тех пор..." - не по-русски. Вопросов много, но уже читать можно по сравнению со статьями, которые я видел раньше. Будем работать над улучшением статей вместе! На Хабре, кстати, явно помечают перевод "переводом" и тут же дают ссылку на оригинал. "Чтобы страна знала своих героев".

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