Я продолжаю ряд статей, посвященных классическим алгоритмам, и сегодня я хотел бы рассказать о Быстрой сортировке (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); } }
Рабочий пример сортировки можно посмотреть тут:
За сим все! Безошибочного Вам кода!
Быстрая сортировка — реализации на PHP и JS: 2 комментария
Добрый день!
Начинающий в программировании.
Будьте добры: поясните, почему используем цикл do..while ?
Спасибо.
Никита, конечно, сама конструкция цикла считается устаревшей, однако здесь нам необходимо, чтобы хотя бы одна итерация цикла отработала. А это позволяют сделать либо do..while, либо for. Здесь do..while скорее для выразительности.