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

В этой статье поговорим о Быстрой сортировке (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);
        } 
    }

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