Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂
Алгоритмы сортировки – это популярная тема, на разбор которой в университетах отводится несколько месяцев. Но зачем вообще в 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.
Комментарии