Быстрые алгоритмы сортировки

Альтернативный вариант quicksort

В дополнение к достаточно сложному для понимания алгоритму разбиения из прошлогодних материалов мы приведём более простую альтернативу

def partition(a, left, right):
  pivot = a[left]  ## или любой другой элемент массива
  index = right-1  ## такой index работает только для a[left] 

  while left < right:
    if a[left] < pivot: left += 1
    else:
      right -= 1
      a[left], a[right] = a[right], a[left]

  a[left], a[index] = a[index], a[left]
  return left


def quicksort(array, left = 0, right = None):
  if right == None: right = len(array)

  if right - left <= 1: return

  pivot_index = partition(array, left, right)
  quicksort(array, left, pivot_index)
  quicksort(array, pivot_index+1, right)

Корректность разбиения partition здесь очевидна:

• элементы с индексами, меньшими left, всегда меньше опорного
• элементы с индексами, не меньшими right, всегда не меньше опорного
• за каждую итерацию цикла разница между right и left уменьшается на 1, поэтому цикл завершается, а right не бывает меньше left
• отсюда, в частности, следует, что right и left в момент обмена находятся в пределах массива

На практике вышеприведённый алгоритм работает примерно на 10% медленнее, чем тот, который приведён в прошлогодних материалах (впрочем, в реальности в чистом виде quicksort редко используется — есть существенно более сложные, но при этом и более эффективные схемы сортировки).