Слишком хорошо, чтобы упустить: алгоритмы сортировки как искусство


Некоторые новости прошлого года заслуживают второго шанса. Вот один из таких алгоритмов – алгоритмы сортировки имеют фундаментальное значение для информатики, и написание собственного кода многому вас научит. Есть много разных подходов к сортировке, но их объединяет то, что они лучше понимаются при визуализации.

(2019-04-28)

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

Если вы пропустили видео о народных танцах студентов Университета Сапиентия, Румыния, которые были загружены на YouTube компанией AlgoRythmics, то у нас есть полная серия здесь.

Последняя визуализация алгоритмов сортировки – это проект Sortraits от Уильяма Трейси. Открытый исходный код по лицензии MIT – это проект по созданию портретов с использованием различных алгоритмов сортировки, включая сортировку по выбору, сортировку вставкой, пузырьковую сортировку и быструю сортировку. Результаты очень поразительны. Вот некоторые из них, которые я был бы счастлив отобразить как произведения искусства с использованием четно-нечетной сортировки, коктейльной сортировки и сортировки Gnome – всех видов, которые для меня в новинку:

Объясняя, как он создавал свои сортировки, Трейси пишет:

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

Я использовал несколько типов начальных списков: пробовал перемешивать списки в случайном порядке. Я пробовал составлять списки в обратном порядке. Я попытался начать с упорядоченного списка и чередовать пиксели из двух половин. Я попытался поменять местами две половинки. Я пробовал поменять местами первую и последнюю трети. Я даже пробовал запускать алгоритмы для уже отсортированного списка – некоторые алгоритмы настаивают на том, чтобы полностью переупорядочить список, а затем вернуть его в порядок!

Я также пробовал визуализировать различия: для каждого пикселя я сравнивал текущее значение пикселя и значение, которое он должен иметь при правильном порядке списка. Если они совпадают, я окрашиваю пиксель в черный цвет. Чем больше они различаются, тем ярче становится пиксель. Области, над которыми нужно работать, подсвечиваются, а области, которые уже отсортированы, затемняются.

Галерея Sortraits содержит подборку наиболее интересных картин Трейси, некоторые из которых окрашены в разные цвета, что “кажется правильным”. Этот под названием Kaliedoscope Pinwheel использует сортировку по четно-нечетному списку, в котором значения были присвоены оттенкам радуги, а не более ярким и темным оттенкам.

Согласно readme проекта Sortrait на GitLab, где вы можете получить доступ к коду проекта и изменить или добавить в него, если хотите, говорится:

Эта кодовая база представляет собой нечестивый союз кода Haskell и сценариев оболочки Bash. Администрация не несет никакой ответственности за ваше здравомыслие, если вы продолжите.

В списке Todo есть следующие выдающиеся пункты:

Может быть, реализовать плавную сортировку. Наверное, не гравитационный. Не уверен в сортировке по терпению, сортировке с голландским флагом, сортировке по американскому флагу и сортировке блоков.

Поэкспериментируйте с разделением выходных значений на неизмененные, измененные и окончательные значения. Каждый раздел может иметь различную цветовую кодировку.

Лично я счастлив просто посмотреть на результат – Haskell и Bash !:

В то время как эти портреты представляют собой статическую интерпретацию различных видов, анимация – хороший способ показать сортировку в действии, см., Например, «Удивительную анимационную демонстрацию сортировки». Галерея Sortraits включает ссылку на анимации, которые послужили источником вдохновения для проекта: Визуализация алгоритмов сортировки, при этом отмечается:

На этой странице много больших анимаций, поэтому не переходите по этой ссылке, если у вас медленное соединение!

Вот видео на YouTube, которое вдохновило на визуализацию различий, используемую в Sortraits:

Еще одним источником вдохновения в проекте стал фильм Тимо Бингманна «Звук сортировки», описанный его создателем как:

Визуализация и «аудибилизация» 15 алгоритмов сортировки за 6 минут.

Видео сортирует случайное перемешивание целых чисел, причем скорость и количество элементов адаптируются к сложности каждого алгоритма:

Бингманн предоставил код, который он использовал для демонстрации Sound of Sorting, на GitHub, и он был широко разветвлен. Это видео, основанное на коде, найденном здесь, представляет собой звук сортировки списка по убыванию с помощью Radix sort, который, по мнению его автора, звучит довольно круто, поэтому поделился им:


Добавить комментарий