Хочешь уверенно проходить IT-интервью?
Мы понимаем, как сложно подготовиться: стресс, алгоритмы, вопросы, от которых голова идёт кругом. Но с AI тренажёром всё гораздо проще.
💡 Почему Т1 тренажёр — это мастхэв?
- Получишь настоящую обратную связь: где затык, что подтянуть и как стать лучше
- Научишься не только решать задачи, но и объяснять своё решение так, чтобы интервьюер сказал: "Вау!".
- Освоишь все этапы собеседования, от вопросов по алгоритмам до диалога о твоих целях.
Зачем листать миллион туториалов? Просто зайди в Т1 тренажёр, потренируйся и уверенно удиви интервьюеров. Мы не обещаем лёгкой прогулки, но обещаем, что будешь готов!
Реклама. ООО «Смарт Гико», ИНН 7743264341. Erid 2VtzqwP8vqy
Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂
Алгоритмы сортировки – это популярная тема, на разбор которой в университетах отводится несколько месяцев. Но зачем вообще в 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.
Комментарии