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