Одной из классических задач, которую ставят перед студентами, изучающими информатику, является сортировка списка элементов. На первый взгляд это совсем не пугающая проблема, на самом деле возможные решения кажутся довольно простыми, и мы все, несомненно, сортировали список в какой-то момент повседневной жизни. Конечно, в какой-то степени это правда. Давайте рассмотрим этот случайно сгенерированный список из 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).