Одной из классических задач, которую ставят перед студентами, изучающими информатику, является сортировка списка элементов. На первый взгляд это совсем не пугающая проблема, на самом деле возможные решения кажутся довольно простыми, и мы все, несомненно, сортировали список в какой-то момент повседневной жизни. Конечно, в какой-то степени это правда. Давайте рассмотрим этот случайно сгенерированный список из 10 целых чисел, например: [7, 8, 6, 2, 2, 8, 10, 4, 3]

Попробуйте отсортировать по возрастанию. На первый взгляд у меня всплывает ряд решений (по общему признанию, мой первый взгляд приходит после того, как я провел последние пару часов за чтением/кодированием алгоритмов сортировки):

1. Переместите наименьшие элементы на передний план (сортировка выбором). Самый простой подход для меня — просто найти минимальный элемент и переместить его на передний план. Затем повторите этот процесс, просматривая список, начиная с индекса один, пока не дойдете до последнего элемента.

2. Сортировка списка слева направо (сортировка вставками).В качестве альтернативы вы можете просто создавать список по одному элементу за раз. Начните с нулевого индекса [7]. Теперь добавьте в индекс один [7, 8]. Затем проиндексируйте два [6, 7, 8]. Продолжайте, пока не дойдете до конца списка.

Оба эти решения будут работать и действительно довольно просты в реализации (максимум 10 строк кода). Но, как это обычно бывает в компьютерных науках, задача на самом деле заключается в разработке решения, которое было бы достаточно масштабируемым и эффективным.

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

Я решил внедрить Quicksort по нескольким причинам:

а) Он демонстрирует оптимальное время выполнения O (n log n) в среднем случае

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

c) Это сортировка, используемая функцией Java Arrays.Sort, которую я считаю отличной поддержкой.

Неформально алгоритм быстрой сортировки работает путем случайного выбора элемента, называемого элементом разбиения, а затем разбивает массив на части (в идеале пополам), меняя местами элементы, меньшие, чем элемент разбиения, слева и больше справа. Продолжайте разбиение левой и правой группами, пока длина разделов не достигнет единицы или нуля. Преимущество заключается в том, что с каждым прогрессивным разделом вам нужно иметь дело только с половиной элементов, как раньше. Ознакомьтесь с этой статьей в Принстоне для более подробного пошагового ознакомления с тем, как работает Quicksort. Повторите это примерно n/2 раза, и мы получим сложность O(n log n). Конечно, в худшем случае, когда каждый выбранный элемент раздела оказывается самым маленьким или самым большим элементом в группе, мы в конечном итоге разбиваем массив на куски из одного элемента и n-1 элементов, по существу сортируя массив по одному элементу за раз в О (n²).

Код:

#Quicksort method
def sort(array, start, end):
 if (start<end):
  p = partition3(array, start, end)
  sort(array, start, p-1)
  sort(array, p+1, end)
#Partitioning code
def partition3(A, lo, hi):
 pivot = A[hi]
 i = lo - 1
 for j in range(lo, hi):
  if (A[j] < pivot):
   i+=1
   temp = A[i]
   A[i] = A[j]
   A[j] = temp
 if (A[hi] < A[i+1]):
  temp = A[i+1]
  A[i+1] = A[hi]
  A[hi] = temp
 return i+1

Производительность

Результаты тестов производительности для своего рода, словом, не впечатляют. Я протестировал сортировку как на небольшом наборе больших массивов, так и на большом наборе маленьких массивов. Ни один из них не дал положительных результатов, при этом сортировка вставками в обоих случаях значительно опережала быструю сортировку. Вот результаты запуска с моего ноутбука.

В общем, это был отрезвляющий урок о разрыве между алгоритмической сложностью и реальной производительностью. Надеюсь, мне удастся добавить некоторые оптимизации для быстрой сортировки, а именно переключение на быструю сортировку, когда разделы достигли небольшого входного размера, и переписать разбиение так, чтобы глубину рекурсивных вызовов можно было ограничить до O(log n).