Сегодня мы рассмотрим очень важный алгоритм сортировки: quicksort. Быстрая сортировка - это рекурсивный алгоритм сортировки, использующий стратегию разделяй и властвуй.

Я не буду объяснять, как работает рекурсия, поскольку я уже писал об этом статью.

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

Чтобы добиться этого, я сначала расскажу о основной операции быстрой сортировки: разбиении на разделы. Это работает следующим образом:

>>> A = [6, 3, 17, 11, 4, 44, 76, 23, 12, 30]
>>> partition(A, 0, len(A)-1)
>>> print(A)
[6, 3, 17, 11, 4, 23, 12, 30, 76, 44]

Итак, что здесь произошло и как это работает? Нам нужно выбрать какое-то число в качестве нашей точки поворота. Наша функция разделения принимает 3 аргумента: список, первый элемент в списке и свод. Здесь мы пытаемся добиться того, чтобы при разделении списка все, что слева от оси, было меньше, чем pivot, а все, что справа, больше, чем pivot . Для первого раздела, показанного выше, 30 является нашей точкой опоры. После разделения мы видим, что некоторые элементы изменили положение, но все, что слева от 30, меньше его, а все справа больше, чем это.

Так что это значит для нас? Что ж, это означает, что 30 теперь находится на своей правильной позиции в списке И теперь у нас есть два более простых списка для сортировки. Все это делается на месте, поэтому мы не создаем новые списки.

Посмотрим на код:

def partition(A, p, r):
   q = j = p
   while j < r:
     if A[j] <= A[r]:
       A[q], A[j] = A[j], A[q]
         q += 1
     j += 1
   A[q], A[r] = A[r], A[q]
   return q

return q в конце не обязателен для нашего раздела, но необходим для сортировки всего списка. Приведенный выше код работает по списку A и поддерживает индексы p, q, j, r.

p фиксирован и является первым элементом в списке. r является точкой поворота и является последним элементом в списке. Элементы в диапазоне A [p: q-1], как известно, меньше или равны оси поворота и всем элементам от A [q-1: r-1] больше оси. Изменяются только индексы q и j. На каждом этапе мы сравниваем A [j] с A [r]. Если он больше точки поворота, он находится в правильном положении, поэтому мы увеличиваем j и переходим к следующему элементу. Если A [j] меньше A [r], мы меняем A [q] на A [j]. После этой замены мы увеличиваем q, тем самым расширяя диапазон элементов, которые, как известно, меньше или равны оси поворота. Мы также увеличиваем j, чтобы перейти к следующему обрабатываемому элементу.

Теперь перейдем к части быстрой сортировки. Помните, что это рекурсивный алгоритм, поэтому он будет постоянно вызывать partition (), пока не останется ничего для разделения.

Посмотрим на код:

def quicksort(A, p, r):
   if r <= p:
     return
   q = partition(A, p, r)
   quicksort(A, p, q-1)
   quicksort(A, q+1, r)
   return A

Это так просто. Все, что мы делаем здесь, это проверяем, меньше ли индекс разворота или равен индексу начала нашего списка, который мы хотим разделить. Если это так, мы возвращаемся, поскольку переданный список не нуждается в дальнейшем разделении.

В противном случае мы разделяем список A и снова вызываем quicksort для двух новых вложенных списков.

Быстрая сортировка лучше всего работает с большими списками, которые полностью зашифрованы. Он действительно плохо работает в почти отсортированных списках. Или в нотации Big-O лучший случай (зашифрованный) - O (n log (n)), а в худшем случае (почти или полностью упорядоченный список) - O (n ^ 2).

Эта тема более подробно освещена в нашей новой книге Slither into Python, которую вы теперь можете предварительно заказать всего за 5,99 евро. Наша книга Введение в язык программирования Python для начинающих, разработанная, чтобы превратить вас из полного новичка в компетентного. и опытный программист всего в 22 главах, охватывающих весь спектр тем. Посмотрите ЗДЕСЬ.