Я написал следующий рандомизированный код быстрой сортировки с использованием хвостовой рекурсии. Я хотел увидеть эффект от неиспользования хвостовой рекурсии и хотел узнать, как влияет время выполнения и время выполнения. Как мы можем удалить хвостовую рекурсию из приведенного ниже рандомизированного кода быстрой сортировки?
РЕДАКТИРОВАТЬ:
Есть ли способ вообще удалить второй рекурсивный вызов в quicksort функция. Это будет означать удаление рекурсии хвоста, а также значительно повлияет на время.
Решение
Простой способ удалить хвостовую рекурсию — сделать что-то еще в функции после выполнения рекурсивного вызова. Ниже я изменил функцию, чтобы она возвращала значение вместо void и добавил оператор return для возврата чего-либо после завершения рекурсивного вызова. Это должно оказать минимальное влияние на производительность.
Другие решения
Компиляторы обычно имеют возможность включать и отключать определенные оптимизации.
В случае g ++ и связанных с ним компиляторов вы можете включать и отключать оптимизацию хвостового вызова, используя -foptimize-sibling-calls а также -fno-optimize-sibling-calls опции. Если вы используете другой компилятор, см. Руководство.
Я бы порекомендовал использовать их для сравнения эффекта хвостовой рекурсии, поскольку он позволяет использовать тот же алгоритм.
Быстрая сортировка, естественно, хвостовая рекурсия, поэтому сделать ее без хвостовой рекурсии непросто. С одной стороны, это легко: просто сделайте что-нибудь после вызова рекурсии. Вуаля, алгоритм больше не является хвостовым рекурсивным. Но то, что вы делаете после рекурсии, важно. У него должен быть побочный эффект, иначе он может быть оптимизирован. Но тогда это повлияет на производительность, и вы больше не будете измерять только эффект оптимизации хвостового вызова.
Вот идея. Реализуйте две идентичные функции, которые вместо этого вызывают друг друга, если они сами в хвостовом вызове:
Оптимизацию хвостовых вызовов для взаимно рекурсивных функций все еще возможно, поэтому я не гарантирую, что умный компилятор не поймет, что происходит. Но реализовать оптимизацию будет сложнее, поэтому некоторые компиляторы могут не пытаться это сделать. Проверьте сборку, если хотите быть уверенным. Кроме того, это может оказать некоторое влияние на кэш инструкций, поэтому может повлиять на производительность, а не просто отключить оптимизацию хвостового вызова.
Некоторые из представленных здесь реализаций используют в качестве опорного элемента один из крайних элементов подмассива. Эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра, их время работы становится порядка Θ ( n 2 ) <displaystyle Theta (n^<2>)> 
.
В качестве опорного элемента следует выбирать случайный элемент массива, чтобы получить гарантированное время сортировки Θ ( n log n ) <displaystyle Theta (nlog n)> в среднем. В случае, если использование случайных чисел нежелательно, в качестве опорного элемента можно выбрать, например, элемент в середине массива, но такие алгоритмы всё равно будут работать за Θ ( n 2 ) <displaystyle Theta (n^<2>)> времени на некоторых специально-сконструированных массивах.
Содержание
VBA [ править ]
Работает для произвольного массива из n целых чисел.
C# [ править ]
C [ править ]
Работает для произвольного массива из n целых чисел.
Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.
C# [ править ]
C# с обобщёнными типами [ править ]
Тип Т должен реализовывать интерфейс IComparable .
C# с использованием лямбда-выражений [ править ]
C++ [ править ]
Быстрая сортировка на основе библиотеки STL [ править ]
Для вещественных чисел [ править ]
Java [ править ]
Java с инициализацией и перемешиванием массива [ править ]
и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива).
Java без рекурсии, с использованием стека [ править ]
пошаговый алгоритм с возможностью вывода на экран текущего действия
JavaScript [ править ]
Python [ править ]
Через list comprehension:
Joy [ править ]
PHP [ править ]
Haskell [ править ]
Математическая версия — с использованием генераторов:
Данная версия алгоритма является самой короткой из возможных, но тратит слишком много дополнительной памяти. На практике такой алгоритм использоваться не может. Стоит также отметить, что списки — неудачный выбор для реализации быстрой сортировки.
Common Lisp [ править ]
В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" — она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует "императивные" макросы Common Lisp’а.
Pascal [ править ]
В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его — зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве — он проще и быстрее, хотя, теоретически, может быть хуже.
Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.
Устойчивый вариант (требует дополнительно O(n)памяти)
Быстрая сортировка, нерекурсивный вариант [ править ]
Нерекурсивная реализация быстрой сортировки через управляемый вручную стек. Функции compare и change реализуются в зависимости от типа данных.
Частично рекурсивная реализация [ править ]
Реализация на языке pascal с одной рекурсивной ветвью. После разделения массива меньшая часть сортируется рекурсивным вызовом, а бо’льшая — в цикле. Это гарантирует глубину рекурсии не более lg(N).
Пример реализации алгоритма в объектно-ориентированном стиле с обобщением по типу данных (Generics) [ править ]
В представленной реализации алгоритма быстрой сортировки элементов массива порядок сортировки определяется пользовательской функцией обратного вызова:
которая должна удовлетворять условиям контракта вызова и возвращаемого значения:
Библиотечный модуль [ править ]
Пример использования [ править ]
Prolog [ править ]
Ruby [ править ]
SML [ править ]
This example demonstrates the use of an arbitrary predicate in a functional language.
Быстрая сортировка (англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
| Худшее время |
|---|
O(n log n) (обычное разделение)
или O(n) (разделение на 3 части)
O(n) вспомогательных
O(log n) вспомогательных
Реализация алгоритма на различных языках программирования:
Работает для произвольного массива из n целых чисел.
Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.
Java/C#
C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable
C# с использованием лямбда-выражений
Быстрая сортировка на основе библиотеки STL.
Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)
JavaScript
Python
С использованием генераторов:
Haskell
Математическая версия — с использованием генераторов:
Common Lisp
В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" — она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует "императивные" макросы Common Lisp’а.
Pascal
В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его — зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве — он проще и быстрее, хотя, теоретически, может быть хуже.
Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.
Устойчивый вариант (требует дополнительно O(n)памяти)
Быстрая сортировка, нерекурсивный вариант
Нерекурсивная реализация быстрой сортировки через стек. Функции compare и change реализуются в зависимости от типа данных.