Алгоритм сортировки Quicksort на Python.

Quicksort – один из моих популярных алгоритмов сортировки. По данным Википедии он является наиболее используемым в мире (хотя я думаю, что уже несколько лет его вытесняет новый алгоритм Timsort). Quicksort был изобретен в 1961 году Тони Хоаром. Давайте перейдем непосредственно к сути этого алгоритма.

Как работает Quicksort

Quicksort – это алгоритм работающий по принципу “разделяй и властвуй”. После выбора элемента внутри массива с именем pivot (опорный элемент), этот массив разбивается на две части: первая содержит элементы <= этого pivot, а вторая – элементы > этого pivot.

После выполнения этой первой сортировки становится ясно, что pivot находится в правильном месте, потому что все предшествующие ему <=, а все последующие >. Таким образом, выполнив эту сортировку рекурсивно на двух полученных секциях, мы можем отсортировать весь массив.

Как и другие алгоритмы, Quicksort состоит из двух основных функций:

• Quicksort: функция для рекурсивной сортировки подмассивов
• Partiton: Функция, которая делает всю грязную работу, разделяя заданный массив на две части, как описано выше.

Если сейчас не очень понятно, не переживайте. Дальше мы подробно разберем как все работает. С примерами, картинками и графиками.

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

В этой статье я решил не говорить подробно о самой функции Quicksort из-за ее простоты. А вот на Partition мы потратим чуть больше времени.

Функция Quicksort

def quicksort(array,first,last):
  if first < last:
	   q=partition(array,first,last)
	   quicksort(array,first,q-1)
	   quicksort(array,q+1,last)
Code language: PHP (php)

Как видите, функция очень проста. Принимает на вход массив array, индекс первого элемента первым а индекс последнего элемента последним. После очень простой проверки (строка 2) разбиение выполняется вызовом функции partition(array,first,last). Эта функция возвращает числовое значение (сохраненное в q), которое определяет индекс pivot (который соответствует элементу, уже правильно расположенному в нашем массиве). После чего функция вызывается рекурсивно на двух еще не упорядоченных подпоследовательностях.

Функция Partition

Самой интересной функцией, безусловно, является функция Partition. Первое, что нужно определить, это какой элемент выбрать в качестве опорного, некоторые используют первый элемент последовательности, другие – последний: ничего не меняется.

В этой статье и последующих реализациях, буду использовать второй вариант.

Итак, у нас есть начальный массив A, первый элемент будет A[r], а последний элемент (соответствующий pivot) будет A[p].

Понятно, что анализируемыми элементами являются все элементы, идущие от A[r] к A[p-1]. Эти элементы сравниваются с опорным элементом, чтобы решить, к какому разделу они относятся. При запуске Partition мы можем разделить массив на четыре части:

• Элементы ≤ опорного узла (хранятся в позициях p…i)
• Элементы > опорного узла (хранятся в позициях i+1…j-1)
• Элементы, которые еще не проанализированы (в позициях j…r)
• Сам опорный узел

Что такое i и j? Это индексы, которые мы будем использовать для разделения рассматриваемых участков во время выполнения функции.

В качестве примера рассмотрим выполнение Partition. Мы видим, что j соответствует индексу первого еще не разобранного элемента. Две области, желтая и красная, соответствуют элементам, которые уже были разделены (желтая область содержит ≤-элементы, а красная область содержит >-элементы).

j-й элемент сравнивается с опорным элементом:

• Если элемент больше, просто увеличиваем j (помните, что красная область идет от i+1 до j-1, поэтому, увеличивая j, мы просто вставляем этот элемент в красную область).
• Если элемент меньше или равен, необходимо выполнить три действия:
  • увеличить значение i
  • произвести обмен между A[i] и A[j]
  • увеличить значение j

Пояснение в виде gif анимации.

Теперь мы можем перейти к коду:

def partition(array,p,r):
  x = array[r]
  i = p-1
  for j in range(p,r):
	   if array[j]<=x:
			i=i+1
			array[i],array[j]=array[j],array[i]
  array[i+1],array[r]=array[r],array[i+1]
  return i+1
Code language: PHP (php)

Как видно из приведенного выше кода, все, что вам нужно сделать, это первоначально установить i по индексу -1 первого элемента разбиваемого подмассива, j будет переменной итерации цикла for, которая будет изменяться от p до r. После этого на каждой итерации необходимо выполнить описанные выше шаги. В конце цикла for мы разделим массив на два подмассива и установим опорную точку в правильное положение.

Заключение

Сегодня мы рассмотрели алгоритм, который мне очень нравится. Надеюсь вам было полезно.