Написать пост

Радужная визуализация алгоритмов сортировки

Аватар Типичный программист

Обложка поста Радужная визуализация алгоритмов сортировки

Если у вас есть ограничения по восприятию цвета, то доступна версия для дальтоников.

Во всех визуализациях каждый ряд или столбец пикселей представляет собой отдельный независимый массив, который сортируется одновременно с остальными.

Сортировка пузырьком

Алгоритм считается учебным и практически не применяется вне учебной литературы. На каждом проходе сравниваются два соседних элемента, и если их порядок неправильный, они меняются местами. В итоге элемент как бы всплывает на своё место.

Описание алгоритма на Википедии

 

Она же, но увеличенная и замедленная версия, чтобы было проще понять суть:

Сортировка перемешиванием

Её также называют шейкерной или коктейльной, своего рода разновидность пузырьковой. И из визуализации сразу понятно, почему.

Сортировка вставками

В этой сортировке все элементы массива просматриваются по одному, и каждый помещается в нужное место в уже отсортированной части. Забавно, что вставки куда больше похожи на всплывающие пузырьки, чем в пузырьковой сортировке.

Сортировка Шелла

Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами, это сортировка вставками с предварительными «грубыми» проходами.

Сортировка расчёской

Эта сортировка по сути является улучшенным пузырьковым алгоритмом. Основная идея в том, что промежуток между сравниваемыми элементами может быть больше, чем единица, что позволяет значительно улучшить эффективность.

Сортировка слиянием

Этот алгоритм разбивает всю область сортировки на части и сортирует их рекурсивно, а затем сливает. На визуализации левая часть использует рекурсию, уходящую в глубину, а в правой — в ширину. Оба способа обхода занимают в итоге одинаковое время.

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

Этот алгоритм может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) или тонет (max-heap) по многим путям, в зависимости от того, какой тип двоичной кучи применяется. В визуализации можно наглядно сравнить скорость в одном и другом случае. Можете поупражняться и попробовать объяснить, почему один из вариантов быстрее.

Быстрая сортировка

Она же сортировка Хоара — один из самых популярных алгоритмов из-за своей универсальности и средней скорости. Принципиальное отличие от сортировок прямыми обменами (например, той же пузырьковой) состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии, и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных методов.

 

И тот же алгоритм, но не на случайных данных, а на массиве, отсортированном в обратном порядке:

Поразрядная сортировка

Этот алгоритм сортирует числа за линейное время по разрядам. Существует два варианта: most significant digit (MSD, на визуализации слева) и least significant digit (LSD, справа). При MSD сортировке сначала сортируются старшие разряды, затем младшие, а при LSD всё наоборот.

Битонная сортировка

Этот алгоритм предназначен для параллельной сортировки данных на разных вычислительных узлах. В основе лежит понятие «битонной последовательности», отсюда и название. Если данные позволяют разбиение для параллельной обработки, этот способ может сработать намного быстрее других.

 

Она же, чуть ближе и медленнее:

Сравнение алгоритмов по скорости

Сделав столько визуализаций, было бы странно не заставить их соревноваться между собой.

На случайном наборе данных, как и ожидалось, коктейльная сортировка (слева) заметно проигрывает. Вторая слева — сортировка вставками, далее Шелла, и самая правая — сортировка расчёской:

 

Те же алгоритмы, но на отсортированном в обратном порядке массиве. Заметно, что метод вставок сработал ещё медленнее:

 

Теперь сравним алгоритмы, работающие за O(n log n). Быстрая сортировка слева, затем пирамидальная, слиянием, и самая правая — поразрядная.

 

Те же алгоритмы ещё раз, но на этот раз в массиве только 8 уникальных значений. В этот раз быстрая сортировка справилась хуже.

 

Подробнее про алгоритмы сортировки для начинающих вы можете прочитать в нашей статье из цикла «Алгоритмы и структуры данных».

Также посмотрите другие визуализации алгоритмов сортировки, больше ориентированные на учебные цели.

Следите за новыми постами
Следите за новыми постами по любимым темам
26К открытий26К показов