Max Home IndustryНекоторые новости прошлого года заслуживают второго шанса. Вот один из таких алгоритмов — алгоритмы сортировки имеют фундаментальное значение для информатики, и написание собственного кода многому вас научит. Есть много разных подходов к сортировке, но их объединяет то, что они лучше понимаются при визуализации.
(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, который, по мнению его автора, звучит довольно круто, поэтому поделился им: