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

Сегодня мы снова возьмём за основу stupid sort и внесём в неё другое маленькое, но существенное изменение. В результате получим совершенного другой эволюционный ряд сортировочных алгоритмов.

image: эволюция

Глупая сортировка

Кому лень смотреть первую серию, напомню, что из себя представляет глупая сортировка. Обходим по порядку массив и, встретив два неотсортированных соседа, меняем их местами. Затем возвращаемся на старт и «наша песня хороша, начинай сначала». Если в этой сортировке вместо возвращения просто идти дальше, то в получаем «пузырёк», который, как оказалось, тоже можно совершенствовать до бесконечности O(n log n).

Теперь поступим иначе. Обменяв два элемента, мы изменили порядок в массиве, и нужно как-то выяснить не вступает ли новое расположение в диссонанс с теми элементами, которые мы проверили ранее. Не будем прыгать в начало массива, не станем идти вперёд, а сделаем шаг назад. Если там теперь тоже не отсортировано, то установим строгую очерёдность по старшинству и сделаем ещё шаг назад. И так будем отступать до тех пор, пока не достигнем отсортированной части массива. После этого снова можно двигаться дальше.



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

Гномья сортировка

image: голландский садовый гном

Хотя гномам этот способ известен уже много столетий, человеческая раса о нём узнала совсем недавно. Уже 55 лет как человечество использовало сортировку слиянием, прошло 40 лет как стала известна быстрая сортировка, уже спустя 35 лет как разработана пирамидальная сортировка – и вот, только в 2000 году, этот бесхитростный, практически детский приём, был исследован Диком Груном:

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

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



Так немного быстрее, хотя принципиально это временную сложность не улучшает, она как была так и остаётся O(n²). Но зато это приводит нас не только к новому способу сортировки, а даже к целому новому классу сортировок. И имя этой группе алгоритмов – «Сортировки вставками».

Сортировка простыми вставками

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

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



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

Временная сложность у этой сортировки O(n²), но не это главное. Сортировка вставками, судя по всему — наиболее эффективный вариант для почти отсортированных массивов. Этот факт используется в некоторых сложных алгоритмах сортировки. Помнится, я уже когда-то рассказывал про FlashSort, там при помощи вероятностного распределения быстро создаётся почти отсортированный массив, который затем доупорядочивается сортировкой вставками. Сортировка вставками используется в финальной части JSort, где путём построения неполной кучи массив оперативно почти сортируется. Timsort начинает сортировку массива с нахождения в нём почти упорядоченных отрезков, они также сортируются вставочным методом, а затем объединяются модифицированной сортировкой слиянием.

Как изволите видеть, хотя сортировка вставками сама по себе работает медленно, её сфера применения очень широка.

Ну, раз столь много букв написано про insertion sort, то рассказ будет не полным, если не сказать пару добрых слов про алгоритм, который называется…

Сортировка Шелла

Про сортировку Шелла уже есть статья на Хабре, поэтому буду очень краток.

Позавчера уже писал как из очень медленного «пузырька» можно сделать очень быструю «расчёску». Для этого сначала нужно сравнивать не соседей, а элементы, между которыми достаточно внушительное расстояние. Это позволяет на начальном этапе маленькие значения закинуть поближе к началу массива, большие – поближе к концу. Затем уменьшая разрыв, уже наводить в массиве локальные порядки.

Shell sort использует ту же стратегию. Сортируем вставкой подгруппы элементов, но только в подгруппе они идут не в ряд, а равномерно выбираются с некоторой дельтой по индексу. Методично уменьшая расстояние между элементами этих несвязных подмножеств, мы сортируем уже намного быстрее.



Временная сложность у «шелла» – достаточно сложный вопрос. Дело в том, что до сих пор нет строгой формулы, по которой строится оптимальный числовой ряд изменяющихся расстояний между элементами в подгруппах. Последовательность строится эмпирически, на основании многочисленных тестов с различными входными данными и последнее наилучшее уточнение для вышеупомянутых «дельт» было определено в 2001 году:

1, 4, 10, 23, 57, 132, 301, 701.

Сортировку Шелла придумал, как ни странно, Дональд Шелл в 1959 году. В 2014-м автору, кстати, исполняется 90 лет, живёт и здравствует до сих пор, недавно в третий раз женился. Так что, изобретайте алгоритмы, держите мозги в тонусе – и переживёте 3-х жён полноценная многолетняя творческая деятельность Вам обеспечена.

Ссылки

Алгоритмы сортировко в Википедии
Sorting Algorithm on Wikipedia
Пузырьковая сортировка и все-все-все
И снова про сортировки: выбираем лучший алгоритм
Реализации сортировок на Розетте