FAQ Infinity

Быстрая сортировка без рекурсий

Быстрая сортировка – это один из наиболее эффективных алгоритмов сортировки. Он использует метод «разделяй и властвуй», который заключается в том, что исходный массив разбивается на поразрядные части и каждая часть сортируется отдельно.

В классической реализации быстрой сортировки используется рекурсия. Однако, рекурсивная реализация может привести к проблемам с памятью при работе с большими массивами. Поэтому хотелось бы предложить альтернативную реализацию быстрой сортировки без рекурсии.

Идея алгоритма

Идея алгоритма заключается в использовании стека для хранения интервалов массива, которые еще не отсортированы. Алгоритм начинает с того, что добавляет в стек всю последовательность непросмотренных элементов, начиная со стартового индекса и заканчивая индексом последнего элемента массива. Затем, пока стек находится не пустым, будем извлекать из него интервалы и производить разбиение на 2 части, в соответствии с выбранным элементом-опорным.

Описание алгоритма

  1. Создаем стек и инициализируем его значениями левой и правой границы массива.
  2. Пока стек не пустой, извлекаем интервал и разбиваем его на 2 подмассива, используя выбранный опорный элемент.
  3. Если размер подмассивов > 1, и мы не дошли до последнего элемента - добавляем в стек левый и правый подмассив.
  4. Поскольку сортировка происходит «in place», то нет необходимости сохранять новые интервалы.
  5. Когда интервал сделал свой путь через стек и закончился – он гарантированно отсортирован.

Реализация на Python

def partition(nums, left, right):
    pivot = nums[left] # опорный элемент
    i = left + 1
    j = right
    
    while True:
        while i <= j and nums[i] <= pivot:
            i += 1
        while i <= j and nums[j] >= pivot:
            j -= 1
        if i <= j:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            break
    nums[left], nums[j] = nums[j], nums[left]
    return j


def quick_sort_iterative(nums):
    if not nums:
        return []

    stack = [(0, len(nums) - 1)]
    
    while stack:
        left, right = stack.pop()
        if left < right:
            pivot_index = partition(nums, left, right)
            stack.append((pivot_index + 1, right))
            stack.append((left, pivot_index - 1))
    
    return nums

Заключение

Быстрая сортировка без рекурсии позволяет эффективно сортировать массивы больших размеров, решая проблемы, связанные с ограниченным размером стека вызовов. Реализация требует дополнительного времени на добавление и извлечение элементов из стека, однако, это не влияет на асимптотику времени работы алгоритма.