Источник: Imgur
Если у вас есть ограничения по восприятию цвета, то доступна версия для дальтоников.
Во всех визуализациях каждый ряд или столбец пикселей представляет собой отдельный независимый массив, который сортируется одновременно с остальными.
Сортировка пузырьком
Алгоритм считается учебным и практически не применяется вне учебной литературы. На каждом проходе сравниваются два соседних элемента, и если их порядок неправильный, они меняются местами. В итоге элемент как бы всплывает на своё место.
Описание алгоритма на Википедии
Error handling this external URL
Она же, но увеличенная и замедленная версия, чтобы было проще понять суть:
Сортировка перемешиванием
Её также называют шейкерной или коктейльной, своего рода разновидность пузырьковой. И из визуализации сразу понятно, почему.
Описание алгоритма на Википедии
Сортировка вставками
В этой сортировке все элементы массива просматриваются по одному, и каждый помещается в нужное место в уже отсортированной части. Забавно, что вставки куда больше похожи на всплывающие пузырьки, чем в пузырьковой сортировке.
Описание алгоритма на Википедии
Error handling this external URL
Сортировка Шелла
Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами, это сортировка вставками с предварительными «грубыми» проходами.
Описание алгоритма на Википедии
Error handling this external URL
Сортировка расчёской
Эта сортировка по сути является улучшенным пузырьковым алгоритмом. Основная идея в том, что промежуток между сравниваемыми элементами может быть больше, чем единица, что позволяет значительно улучшить эффективность.
Описание алгоритма на Википедии
Error handling this external URL
Сортировка слиянием
Этот алгоритм разбивает всю область сортировки на части и сортирует их рекурсивно, а затем сливает. На визуализации левая часть использует рекурсию, уходящую в глубину, а в правой — в ширину. Оба способа обхода занимают в итоге одинаковое время.
Описание алгоритма на Википедии
Error handling this external URL
Пирамидальная сортировка
Этот алгоритм может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) или тонет (max-heap) по многим путям, в зависимости от того, какой тип двоичной кучи применяется. В визуализации можно наглядно сравнить скорость в одном и другом случае. Можете поупражняться и попробовать объяснить, почему один из вариантов быстрее.
Описание алгоритма на Википедии
Error handling this external URL
Быстрая сортировка
Она же сортировка Хоара — один из самых популярных алгоритмов из-за своей универсальности и средней скорости. Принципиальное отличие от сортировок прямыми обменами (например, той же пузырьковой) состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии, и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных методов.
Описание алгоритма на Википедии
Error handling this external URL
И тот же алгоритм, но не на случайных данных, а на массиве, отсортированном в обратном порядке:
Error handling this external URL
Поразрядная сортировка
Этот алгоритм сортирует числа за линейное время по разрядам. Существует два варианта: most significant digit (MSD, на визуализации слева) и least significant digit (LSD, справа). При MSD сортировке сначала сортируются старшие разряды, затем младшие, а при LSD всё наоборот.
Описание алгоритма на Википедии
Error handling this external URL
Битонная сортировка
Этот алгоритм предназначен для параллельной сортировки данных на разных вычислительных узлах. В основе лежит понятие «битонной последовательности», отсюда и название. Если данные позволяют разбиение для параллельной обработки, этот способ может сработать намного быстрее других.
Описание алгоритма на Википедии
Error handling this external URL
Она же, чуть ближе и медленнее:
Error handling this external URL
Сравнение алгоритмов по скорости
Сделав столько визуализаций, было бы странно не заставить их соревноваться между собой.
На случайном наборе данных, как и ожидалось, коктейльная сортировка (слева) заметно проигрывает. Вторая слева — сортировка вставками, далее Шелла, и самая правая — сортировка расчёской:
Error handling this external URL
Те же алгоритмы, но на отсортированном в обратном порядке массиве. Заметно, что метод вставок сработал ещё медленнее:
Error handling this external URL
Теперь сравним алгоритмы, работающие за O(n log n). Быстрая сортировка слева, затем пирамидальная, слиянием, и самая правая — поразрядная.
Error handling this external URL
Те же алгоритмы ещё раз, но на этот раз в массиве только 8 уникальных значений. В этот раз быстрая сортировка справилась хуже.
Error handling this external URL
Подробнее про алгоритмы сортировки для начинающих вы можете прочитать в нашей статье из цикла «Алгоритмы и структуры данных».
Также посмотрите другие визуализации алгоритмов сортировки, больше ориентированные на учебные цели.
Хинт для программистов: если зарегистрироваться на соревнования Huawei Honor Cup, бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.
Перейти к регистрации
