Данный материал представляет собой обзор и анализ того, как в литературе и в цифровых ресурсах изображают рекурсивные сортировки — главным образом сортировку слиянием и быструю сортировку (сортировку Хоара).

Анализ литературы

Анализ литературы затруднён тем, что в некоторых книгах вовсе нет изображений, в иных — одна сортировка может сопровождаться иллюстрациями, а другая нет. Классики в части быстрой сортировки показывают прямой ход рекурсии ^{[Ахо, 236]}. Обратный ход довольно тривиален и не подразумевает каких-то манипуляций с данными.

Как ни странно, Никлаус Вирт весьма туманно показывает нерекурсивную часть сортировки слиянием ^{[Вирт, 129]}.

Для книги, пожалуй, самый адекватный способ представления сортировки слиянием таков ^{[Скиена, 141]}:

Он отображает прямой ход и операции слияния. Но тот же автор не вполне ясно маркирует элементы в массиве, когда речь идёт о быстрой сортировке ^{[Скиена, 144]}.

Некоторые авторы сначала показывают массив и рекурсию абстрактно ^{[Круз, 366]}.

Некоторые — абстрактно, а затем конкретно ^{[Каррано, 434, 435, 443]}.

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

Часть авторов дают только конкретные примеры ^{[Рафгарден, 188][Стивенс, 149][Луридас, 366][Седжвик, 322, 287]}.

Сортировка слиянием.

Быстрая сортировка.

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

Прямой ход рекурсии в быстрой сортировке легко изобразить. Если мысленно спроецировать выделенные элементы на один ряд, станет видно, как массив постепенно упорядочивается ^{[Хайнеман, 97]}.

Некоторые из авторов систематически выбрасывают множество промежуточных рекурсивных вызовов (без многоточий или других обозначений), что можно неверно интерпретировать ^{[Рубио-Санчес, 191, 192, 195]}.

В некоторых современных изданиях, по характеру схожих с научно-популярными, сосредотачиваются на тривиальных случаях, показывают, как массив разбивается в зависимости от выбранного опорного элемента ^{[Бхаргава, 85, 89]}.

Однако промежуточным вызовам должного внимания не уделяется ^{[Бхаргава, 90]}.

Редкие случаи

Редкий вариант, который нужно отметить — список вместо массива в сортировке слиянием ^{[Круз, 358]}.

Также редкий (практически уникальный) случай — трассировка вызовов ^{[Луридас, 374]}.

Помимо дерева сортировки ^{[Луридас, 376]}.

Тот же автор в некоторых примерах вместо чисел и букв использует обозначения карт ^{[Луридас, 373]}.

Затруднительные случаи

Некоторые авторы дают ребусы ^{[Клейнберг, 240]}.

Что имеет в виду автор, когда в одном ряду (на одном уровне рекурсии быстрой сортировки) вводит четыре вида обозначений и стрелки ^{[Луридас, 378]}?

В одном из источников можно найти пример «динамических характеристик» быстрой сортировки ^{[Седжвик, 294, 301, 295]}. Столбцы обозначают вид данных: произвольные, данные с распределением Гаусса, почти упорядоченные, почти упорядоченные в обратном порядке и произвольные файлы с десятью различными значениями ключей.

Второй пример — процесс разбиения на «подфайлы» в ходе сортировки 200 элементов (с отсечением файлов меньше 16 элементов). Это даёт примерное представление о числе сравнений.

И там же — размер стека: для файлов с произвольной организацией (первая и вторая колонки) и частично упорядоченного (третья колонка).

Анализ интернет-ресурсов

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

Рассмотрим пример с сортировкой слиянием.

На последнем этапе рекурсивного разбиения получается следующее изображение.

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

Самым наглядным вариантом могла бы быть управляемая пользователем анимация. В некоторых случаях можно задавать скорость анимации и входные данные (www.thinkingincrowd.me/algorithm, sorting.at). Затруднения вызывает форма представления данных — вертикальные линии или окружности.

Разного рода сравнения «динамических характеристик» ( imgur.com/gallery/GD5gi, toptal.com/developers/sorting-algorithms), как уже было сказано, удобны только для сравнения разных методов и входных данных.

Алгоритмы даже можно «послушать» (youtube.com/watch?v=GIvjJwzrHBU), но польза такого представления весьма сомнительна.

Самый экзотический пример — танцы (youtube.com/watch?v=ywWBy6J5gz8).

Заключение

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

Пример должен быть конкретным — с числами или буквами. Столбцы, окружности и иные варианты трудно сравнивать визуально. Каждый раз числа должны быть одинаковыми.

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

Если рассматриваются нетипичные случаи, например, список вместо массива в сортировке слиянием, то он должен приводиться наряду с типичным.

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

Список литературы

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы.: Пер. с англ.: М.: Издательский дом «Вильямс», 2003. — 384 с.: ил. — Парал. тит. англ.
2. Бхаргава А. Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. — СПб.: Питер, 2017. — 288 с.: ил. — (Серия «Библиотека программиста»)
3. Вирт Н. Алгоритмы и структуры данных / Пер. с англ. Д.Б. Подшивалова. — М.: Мир, 1989. — 360 с.
4. Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. Классика Computer Science / Пер. с англ. Е. Матвеева. — СПб.: Питер, 2016. — 800 с.: ил. — (Серия «Классика computer science»)
5. Круз Р. Л. Структуры данных и проектирование программ [Электронный ресурс] / Р. Л. Круз; пер. с англ. — 2-е изд. (эл.) — М.: БИНОМ. Лаборатория знаний, 2014. — 765 с.: ил. — (Программисту)
6. Каррано Ф., Причард Дж. Абстракция данных и решение задач на C++. Стены и зеркала, 3-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 848 с.: ил. — Парал. тит. англ.
7. Луридас П. Алгоритмы для начинающих: теория и практика для разработчика / Панос Луридас; [пер. с англ. Е.М. Егоровой]. — Москва: Эксмо, 2018. — 608 с. — (Мировой компьютерный бестселлер)
8. Рафгарден Т. Совершенный алгоритм. Основы. — СПб.: Питер, 2019. — 256 с.: ил. — (Серия «Библиотека программиста»)
9. Рубио-Санчес М. Введение в рекурсивное программирование / Пер. с англ. Е. А. Борисова. — М.: ДМК Пресс, 2019. — 436 с.: ил.
10. Седжвик Р. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах: Пер. с англ./Роберт Седжвик. — СПб: ООО «ДиаСофтЮП», 2003. — 1136 с.
11. Скиена С. Алгоритмы. Руководство по разработке. — 2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург, 2021. — 720 с.: ил.
12. Стивенс Р. Алгоритмы. Теория и практическое применение / Род Стивенс. — Москва: Издательство «Э», 2016. — 544 с. — (Мировой компьютерный бестселлер)
13. Хайнеман Дж., Поллис Г., Селков С. Алгоритмы. Справочник с примерами на C, C++, Java и Python, 2-е изд.: Пер. с англ. — СПб.: ООО «Альфа-книга», 2017. — 432 с.: ил. — Парал. тит. англ.