Хабрахабр

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

80+ алгоритмов сортировки

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

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

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

Примеры генерируемой анимации

Сортировка бинарным деревом

Спагетти-сортировка

Спящая сортировка

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

Делать это мышкой не очень удобно, поэтому фокус ввода окна всегда находится на этой кнопке. Поскольку режим просмотра пошаговый, то для перехода к следующему шагу необходимо нажимать в нём кнопку «Новый шаг». То есть, чтобы переходить к следующим шагам, надо просто не лениться давить клавиатурную 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 Sort — это улучшенный Bubble sort). Аналогичная ситуация с Shaker/Bubble.

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

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

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

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

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

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

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

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

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

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

Теги
Показать больше

Похожие статьи

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть