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

Программист реализовал очередной визуализатор некоторых популярных алгоритмов сортировки и опубликовал результаты на сайте Imgur.
алгоритмы сортировки

Источник: 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, бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации