Я продолжаю ряд статей, посвященных классическим алгоритмам, и сегодня я хотел бы рассказать о Быстрой сортировке (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);
        } 
    }

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

Демо-пример

Ссылка на GitHub

За сим все! Безошибочного Вам кода!