14
Ноя
2019

10 самых популярных алгоритмов сортировки на C#

Алгоритмы сортировки – это популярная тема, на разбор которой в университетах отводится несколько месяцев. Но зачем вообще в 2019 году изучать алгоритмы, если в CLR уже и так встроен и прекрасно работает адаптивный метод Sort() для любых коллекций? А причин для этого даже несколько:

  • Алгоритмы сортировки – достаточно популярный вопрос на собеседованиях. Очень часто просят рассказать принцип работы, а иногда даже и реализовать на листочке.
  • В некоторых специфических случаях собственные алгоритмы способны показывать лучшую производительность по сравнению со стандартной реализацией в .NET.
  • Это отличные задачи для тех, кто уже познакомился с синтаксисом языка и хочет приступить к практике, но не знает, что именно ему делать

Поэтому я предлагаю вам подробно ознакомится с видеокурсом канала CODE BLOG, в котором подробно разобраны сами идеи алгоритмов сортировки, приведен пример реализации на языке C# и через все уроки продемонстрирован процесс разработки приложения для визуализации работы алгоритмов. Код доступен на GitHub.

Сортировка пузырьком (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), что, естественно, не очень хорошо.

Сортировка деревом (Tree Sort)

Данный алгоритм основан на структуре данных двоичное дерево поиска (BST), за что и получил свое имя. Принцип достаточно простой – построить дерево и выполнить его инфиксный обход. Если еще не знакомы с двоичным деревом, то можно посмотреть здесь.

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

Пирамидальная сортировка (Heapsort)

Сортировка кучей является одним из оптимальных и часто используемых на практике алгоритмов сортировки. Выполняется он за линейно-квадратическое время O(n*log n) и при этом является достаточно устойчивым. Принцип его работы, так же как и у предыдущего алгоритма, связан со структурой данных – Двоичная куча (heap). Посмотреть про этот структуру можно в моем видео.

Реализация сортировки достаточно простая – нужно просто построить двоичную кучу с минимальным/максимальным элементом в корне и извлекать из неё корневой элемент до тех пор, пока в ней будут элементы. За счёт балансировки кучи в корне всегда будет следующий по очереди элемент.

Сортировка слиянием (merge sort)

Сортировка слиянием постоянно борется за пальму первенства по скорости со следующим алгоритмом и зачастую даже выигрывает за счёт большей устойчивости. Работает ожидаемо за линейно-логарифмическое O(n*log n) время и применяет принцип "разделяй и властвуй". Вся сортируемая последовательность разбивается пополам на группы до тех пор, пока в каждой из них не будет по два элемента. Затем эта маленькая группа упорядочивается и сливается с другой такой же группой. При слиянии в результирующую коллекцию помещаются по порядку элементы из двух исходных групп. И так до тех пор, пока не останется одна отсортированная последовательность.

Быстрая сортировка (quicksort)

Данная сортировка не зря получила свое имя – зачастую она позволяет выполнить сортировку быстрее любого другого алгоритма. Именно быстрая сортировка чаще всего применяется на практике. Работает за линейно-логарифмическое время O(n*log n). И это был бы идеальный алгоритм, если бы не одно «но»: в редких случаях он может деградировать до сортировки пузырьком с квадратичным временем O(n*n). Принцип работы алгоритма связан с выбором опорного элемента, относительно которого выполняется сортировка. Условно коллекция делится пополам относительно его, и все, что меньше опорного элемента, перемещается влево от него, все, что больше – вправо. Все работает прекрасно, когда значение опорного элемента близко к середине, но если он постоянно оказывается максимальным или минимальным, то результаты оказываются плачевными.

Это далеко не все алгоритмы сортировки, которые были рассмотрены в видео. Например, я не упомянул поразрядную сортировку, которая работает за линейное O(n) время, но имеет определенные ограничения. Найти все видео можно по ссылке или в моем блоге https://shwanoff.ru.

Share

Тебе может это понравится...