635
правок
Изменения
→Нерекурсивная реализация быстрой сортировки
s.push(i + 1, r)
s.push(l, i - 1)
В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит \log n, а в худшем случае вырожденного разделения она вообще будет не более n — вся обработка пройдёт в цикле первого уровня рекурсии.
===Улучшенная быстрая сортировка===
