Сортировки всех времён и народов

То, о чём так долго говорили большевики и к чему я с разным темпом шёл несколько лет, наконец-то свершилось. Несколько лет назад написал небольшой макрос, чтобы создавать алгоритмическую gif-анимацию для хабрастатей. Со временем мой скромный инструмент разросся до внушительных размеров, который не стыдно теперь явить миру.

Итак, встречайте.

AlgoLab — Excel-приложение (то есть файл Excel с макросами), в котором можно в пошаговом режиме ознакомиться с алгоритмами сортировок. А также есть возможность подготавливать gif-анимацию.

Всего 4 листа — 2 основных и 2 так, информационных. Вот они:

Лист sort		Лист process
Лист Сортировки		Лист График

_{При клике по картинке откроется полноформатное изображение}

• Лист sort. На этом листе можно быстро сформировать массив и выбрать алгоритм сортировки.
• Лист process. Тут пошагово наблюдаем, как работает тот или иной алгоритм.
• Лист Сортировки. Здесь собрана сводная информация об алгоритмах.
• Лист График. Также приведён планируемый график выхода статей о сортировках.

Ознакомимся с этими листами подробнее.

Лист sort

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

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

Слева в верхней части нужно указать основные характеристики для генерируемого массива:

Размер, должны ли быть значения в массиве неповторяющимися (0 — нет, 1 — да), чему равны минимальный и максимальный элементы в массиве. В макросах VBA включена вандалоустойчивость к вводимым данным, так что можно вводить и какие-то некорректные значения. В этом случае приложение само определит, чему должна равняться та или иная характеристика.

А также опция для определения — надо ли пошагово выполнить алгоритм (= 1) или же можно применить сортировку к структуре и показать только конечный результат (= 0). Разумеется, само excel-приложение создано, чтобы именно в режиме step-by-step пронаблюдать весь процесс, поэтому значение обычно тут равно единице. Но иногда я при тестировании обнуляю эту опцию, чтобы просто проверить, работает ли вообще новый алгоритм, который я добавляю в AlgoLab.xlsm (то есть, мне прежде всего надо увидеть, является ли его конечным результатом отсортированный массив, не тратя время на просмотр визуализации).

Чуть правее располагается область, в которой можно указать, насколько именно не отсортированы элементы в генерируемом неотсортированном массиве.

Сгенерировать случайно перемешанный массива? А может, расположить элементы в убывающем порядке? Или же сделать массив почти отсортированным (а также указать коэффициент почти отсортированности)?

Чтобы выбрать любой из этих способов — нужно просто щёлкнуть мышкой по ячейке с пунктом. В результате в первой строке заново перегенерируется массив. Выбранная ячейка при этом окрасится в синий цвет.

Ещё левее располагается территория, которая понядобится если нужно не просто полюбоваться визуализацией, но и покадрово сохранить весь процесс в виде изображений.

Во-первых, нужно указать, экспортировать ли вообще этапы сортировки в изображения (= 0, если нет, =1 если да, при этом эта опция «одноразовая», то есть сбрасывается в нулевой значение после окончания сортировки). Во-вторых, нужно указать формат изображений (возможны только 4 варианта: GIF, JPG, PNG и BMP. Последний вариант даёт самый качественный результат, поэтому рекомендую именно его). В-третьих, нужно указать путь к папке, куда сохранять картинки (щёлкните по этой ячейке и откроется диалоговое окошко для выбора директории). Потом идёт ячейка, которую макрос заполняет сам — идентификатор сессии (нужен для уникального названия подпапки, чтобы сохранять кадры именно данного применения сортировки). А также надо правильно указать область захвата (координаты верхней левой и нижней правой ячеек, именно ими и будет ограничиваться сохранённые кадры — не копировать же весь лист?)

Ну, а в самой правой части Вы обнаружите ячейку «Сортировать» (выполняющую функцию кнопки запуска процесса, при выборе сортировки и генерации массива нужно просто щёлкнуть по ней).

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

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

Из более чем 80-ти алгоритмов на сегодняшний день доступна примерно половина из них. Пока нереализованные имеют бледный вид по сравнению с уже реализованными. Какие-то ещё не успел сделать (и даже не приступил к реализации). Какие-то написаны и протестированы и очень скоро будут доступны (в частности, у меня готовы почти все сортировки вставками, однако я их буду добавлять в приложение по мере выпуска хабрастатей по этим сортировкам в ближайшие недели и выкладывать в общий доступ обновлённый AlgoLab.xlsm — а что поделать, не хочу спойлерить новые эпизоды своего сериала).

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

А вот в эту область при выборе алгоритма загружается сводная информация про него. Сведения берутся из листа «Сортировки», они макросом подтягиваются автоматически. Кстати, если в этой области менять текст, то на листе-первоисточнике он будет изменяться тоже.

Сортировок, как видите достаточно много. Чтобы не запутаться во всём этом великолепии, они разбиты по классам, в зависимости от того, какой принципиальный метод упорядочивания данных используется. Что же это за классы?

• Случайные сортировки. Элементы массива в случайном порядке перемешиваются и это продолжается до тех пор пока структура внезапно не упорядочится.
• Сортировки обменами. Организовывается тотальное попарное сравнение (и обмен) элементов массива.
• Сортировки вставками. Перебираются элементы и каждый вставляется на своё место.
• Сортировки выбором. В подмассиве выбирается максимальный элемент, который вставляется в конец подмассиваа. Затем к оставшейся неотсортированной части повторяется та же процедура.
• Сортировки слиянием. Ищутся упорядоченные подмассивы, которые соединяются друг с другом.
• Сортировки распределением. Элементы распределяются по классам до тех пор пока это не приведёт к желаемому результату.
• Гибридные сортировки. Комбинируются методы обменных, вставочных, выборных и распределительных алгоритмов.
• Параллельные сортировки. Алгоритмы, где предусмотрена параллельная обработка разных частей массива.
• Сортировочные сети. Массив пропускается сквозь сортировочную сеть, на выходе он упорядочен.
• Прочие сортировки. Псевдоалгоритмы, шуточные и просто экстравагантные сортировки.

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

Лист process

Собственно, при генерации массива, выборе алгоритма и нажатия на кнопку «Сортировать» макрос перебрасывает на этот лист. Именно здесь и совершается таинство упорядочивания данных.

Во время всего процесса вверху Вас будет сопровождать вот это чудное окошко:

Поскольку режим просмотра пошаговый, то для перехода к следующему шагу необходимо нажимать в нём кнопку «Новый шаг». Делать это мышкой не очень удобно, поэтому фокус ввода окна всегда находится на этой кнопке. То есть, чтобы переходить к следующим шагам, надо просто не лениться давить клавиатурную Enter (никаких других телодвижений не потребуется).

Кнопка «Завершить» выводит процесс из пошагового просмотра. Алгоритм молча доделает своё дело и покажет только конечный результат. Завершающий этап работы сортировки Вы не увидите.

Кнопка «Прервать» полностью останавливает работу макросов на данном шаге.

Кнопка «Снимок» позволяет сохранить скриншот именно этого шага. Картинку потом найдёте в той папке, что указана в настройках на листе sort.

Лист Сортировки

Тут хранится большущая таблица со всяческими знаниями о сортировках. Как помните, отсюда подтягивается информация при выборе сортировки на листе sort. Каюсь, пока качество заполнения так себе, не хватило усидчивости, дабы кропотливо внести максимальное количество корректных данных. Надеюсь наверстать в самом ближайшем будущем.

Лист График

На этом листе можно ознакомиться с моими фантазиями о датах ближайших выходов хабрастатей о сортировках.

Рассказывать про алгоритмы буду в таком порядке.

Обмены → Вставки → Выбор → Слияние → Распределение →
→ Гибриды → Параллельные → Сетевые → Случайные

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

1. Описание класса сортировок. Вводная, основные нюансы, присущие всем сортировкам класса, базовые общеизвестные сортировки класса. Обычно эти вступительные статьи будут содержать достаточно общеизвестную информацию. Но всё равно постараюсь, чтобы скучно не было.
2. Некоторые малоизвестные сортировки класса. Тут буду радовать Вас новым материалом, про который практически нет информации на русском языке. А кое-что не найдёте даже и на английском. Отдельных статей не будет только о сортировках обменами, ибо там уже давным-давно нет интересного эксклюзива.
3. Практическое сравнение сортировок класса между собой. Для каждой группы алгоритмов будет финальная статья, посвящённая тестированию сортировок на различных наборах данных. Здесь обещаю немало удивительных открытий!

Практическое сравнение сортировок

Планировалось сравнивать только python-реализации алгоритмов. Однако, увидев первые результаты на примере гномьей сортировки, пришёл к выводу, что они будут выдавать превратное представление об относительной скорости.

У python своя система доступа к памяти переменных (особенно если эти переменные присваиваются друг другу), из-за чего оптимизированные алгоритмы могут работать медленнее.

Гномья сортировка	Оптимизированная гномья сортировка
def gnome(data): i, size = 1, len(data) while i < size: if data[i - 1] <= data[i]: i += 1 else: data[i - 1], data[i] = data[i], data[i - 1] if i > 1: i -= 1 return data	def gnome_opt(data): i, j, size = 1, 2, len(data) while i < size: if data[i - 1] <= data[i]: i, j = j, j + 1 else: data[i - 1], data[i] = data[i], data[i - 1] i -= 1 if i == 0: i, j = j, j + 1 return data
10 массивов по 1000 элементов в каждом
Общее время: 3.39134 сек.	Общее время: 5.6809 сек.

Аналогичная ситуация с Shaker/Bubble. Пузырьковая сортировка вопреки ожиданиям работает быстрее чем шейкерная (хотя Shaker Sort — это улучшенный Bubble sort).

Для контроля я тестировал сортировки и на PHP (в основном работаю на этом языке, поэтому альтернативный тест быстрее и проще всего смог именно создать на нём). Там уже ситуация «нормальная» — оптимизированный «гном» на всех наборах данных работает явно быстрее, чем обычный.

Однако и у PHP репутация «несовершенного» и медленного средства, поэтому решил что и он не подходит для глобальных выводов. Чтобы свести возможные упрёки [в выборе неподходящего языка для тестирования реальной скорости] к минимуму решил основные тесты делать также на Java. Однако столкнулся с дефицитом своих знаний для этого языка. Увы, тут не срослось.

Таким образом, тестирование будет сразу на трёх двух языках:

• Python. Прежде всего этот язык наиболее подходит для описания алгоритма. Раз уж есть работающие корректные функции, тогда и замерим время для них. Но результаты будет несколько сомнительными.
• PHP. Изначально не собирался как-либо в серии статей использовать этот язык. Но раз уж написал среду на нём для тестирования сортировок и сами реализации на этом ЯП имеются, то почему бы и да. Практические результаты, по которым можно судить об относительной эффективности алгоритмов более адекватны по сравнению с Питоном.
• Java. Именно по результатам на Джаве будем делать основные выводы.

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

FAQ

Уже предвижу некоторые вопросы из зала, отвечу сразу.

Почему программа для визуализации алгоритмов реализована именно в Excel?

Так в своё время было быстрее и проще всего (для меня). Решётчатое пространство электронных таблиц на поверку оказалось весьма и весьма удобным готовым решением для визуализации работы с массивами.

Ок, разберём все эти сортировки. Что дальше?

Буду на основании AlgoLab делать визуализации для деревьев, графов. Скатерть Улама, муравей Лэнгтона, вот это всё. Есть ещё заготовки для 2048 (ИИ играет с помощью минимакса и метода Монте-Карло — доделать надо). Работы — непочатый край.

Ссылки

Скачать AlgoLab.xlsm можно с Google-Диска.

Автор: valemak

Источник