Алгоритмы сортировки – это популярная тема, на разбор которой в университетах отводится несколько месяцев. Но зачем вообще в 20?? году изучать алгоритмы, если в CLR уже и так встроен и прекрасно работает адаптивный метод Sort() для любых коллекций? А причин для этого даже несколько:
- Алгоритмы сортировки – достаточно популярный вопрос на собеседованиях. Очень часто просят рассказать принцип работы, а иногда даже и реализовать на листочке.
- В некоторых специфических случаях собственные алгоритмы способны показывать лучшую производительность по сравнению со стандартной реализацией в .NET.
- Это отличные задачи для тех, кто уже познакомился с синтаксисом языка и хочет приступить к практике, но не знает, что именно ему делать
Сортировка пузырьком (Bubble Sort)
Один из наиболее известных и часто спрашиваемых на собеседованиях алгоритмов сортировки. Работает за квадратичное время O(n*n). Принцип работы достаточно прост: последовательно сравниваются два рядом стоящих элемента, и если левый больше правого, то они меняются местами, после чего сравниваются следующие элементы. И так повторяется до тех пор, пока все элементы не будут упорядочены.
Шейкерная (коктейльная) сортировка (Cocktail Sort)
Модифицированный и немного улучшенный алгоритм пузырьковой сортировки, при котором обмен выполняется в двух направлениях – наибольшие элементы перемещаются в правую сторону, а во время обратного движения наименьшие движутся в левую сторону. Выполняется также за квадратичное время O(n*n).
Сортировка вставками (Insertion Sort)
Сортировка вставками – достаточно простой в реализации и понятный для понимания алгоритм, который прекрасно работает на частично упорядоченных последовательностях и когда сортируемая коллекция последовательно заполняется элементами. Работает, как и рассмотренные ранее алгоритмы, за квадратичное время O(n*n). Элементы последовательно добавляются в отсортированную позицию в нужное место, пока вся коллекция не будет отсортирована.
Сортировка Шелла (Shell Sort)
Данный алгоритм является усовершенствованной реализацией предыдущей сортировки вставками. Идея состоит в том, чтобы сортировать элементы, стоящие на некотором расстоянии друг от друга, что в результате даст частично отсортированную последовательность, которую можно будет легко и быстро отсортировать сортировкой вставками. Несмотря на то, что в худшем случае сортировка также отрабатывает за квадратичное время O(n*n), этот алгоритм обычно показывает значительно лучший линейно-логарифмический результат O(n*log n).
Сортировка выбором (Selection Sort)
Наверное, самый простой с точки зрения понимания алгоритм сортировки – просто последовательно выбирай самый большой элемент из всей сортируемой последовательности. Но, как это часто бывает, чем проще идея и реализация, тем хуже работает. Данный алгоритм работает строго за квадратичное время O(n*n), что, естественно, не очень хорошо.
Сортировка выбором (Selection Sort)
Наверное, самый простой с точки зрения понимания алгоритм сортировки – просто последовательно выбирай самый большой элемент из всей сортируемой последовательности. Но, как это часто бывает, чем проще идея и реализация, тем хуже работает. Данный алгоритм работает строго за квадратичное время O(n*n), что, естественно, не очень хорошо.
Пирамидальная сортировка (Heapsort)
Сортировка кучей является одним из оптимальных и часто используемых на практике алгоритмов сортировки. Выполняется он за линейно-квадратическое время O(n*log n) и при этом является достаточно устойчивым. Принцип его работы, так же как и у предыдущего алгоритма, связан со структурой данных – Двоичная куча (heap). Посмотреть про этот структуру можно в моем видео.
Реализация сортировки достаточно простая – нужно просто построить двоичную кучу с минимальным/максимальным элементом в корне и извлекать из неё корневой элемент до тех пор, пока в ней будут элементы. За счёт балансировки кучи в корне всегда будет следующий по очереди элемент.
Сортировка слиянием (merge sort)
Сортировка слиянием постоянно борется за пальму первенства по скорости со следующим алгоритмом и зачастую даже выигрывает за счёт большей устойчивости. Работает ожидаемо за линейно-логарифмическое O(n*log n) время и применяет принцип «разделяй и властвуй». Вся сортируемая последовательность разбивается пополам на группы до тех пор, пока в каждой из них не будет по два элемента. Затем эта маленькая группа упорядочивается и сливается с другой такой же группой. При слиянии в результирующую коллекцию помещаются по порядку элементы из двух исходных групп. И так до тех пор, пока не останется одна отсортированная последовательность.
Быстрая сортировка (quicksort)
Данная сортировка не зря получила свое имя – зачастую она позволяет выполнить сортировку быстрее любого другого алгоритма. Именно быстрая сортировка чаще всего применяется на практике. Работает за линейно-логарифмическое время O(n*log n). И это был бы идеальный алгоритм, если бы не одно «но»: в редких случаях он может деградировать до сортировки пузырьком с квадратичным временем O(n*n). Принцип работы алгоритма связан с выбором опорного элемента, относительно которого выполняется сортировка. Условно коллекция делится пополам относительно его, и все, что меньше опорного элемента, перемещается влево от него, все, что больше – вправо. Все работает прекрасно, когда значение опорного элемента близко к середине, но если он постоянно оказывается максимальным или минимальным, то результаты оказываются плачевными.
