Изменения

Перейти к: навигация, поиск

Быстрая сортировка

1 байт убрано, 23:00, 14 июня 2016
Нерекурсивная реализация быстрой сортировки
Для выполнения быстрой сортировки можно воспользоваться [[Стек | стеком]], в котором в виде сортируемых подмассивов содержится перечень действий, которые предстоит выполнить. Каждый раз когда возникает необходимость в обработке подмассива, он выталкивается из стека. После разделения массива получаются два подмассива, требующих дальнейшей обработки, которые и заталкиваются в стек.
Представленная ниже нерекурсивная реализация использует стек, заменяя рекурсивные вызовы помещением в стек параметров функции, а вызовы процедур и выходы из них — циклом, который осуществляет выборку параметров из стека и их обработку, пока стек не пуст. Мы помещаем больший из двух подмассивов в стек первым с тем, чтобы максимальная глубина стека при сортировке <tex>N</tex> элементов не превосходила величины <tex>\log n</tex>.
'''void''' quicksort(a: '''int'''[n], '''int''' l, '''int''' r):
'''stack'''< '''pair'''<'''int''','''int'''> > s
s.push(l, r);
635
правок

Навигация