Глупая и не очень сортировки

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

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

Содержание



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

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

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

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

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

Разумеется, люди предложили способ по улучшению, до которого не додумались консервативные лилипуты. Если запоминать место в котором встретилось неотсортированное недоразумение и сделать несколько корректирующих итераций назад, то после наведения порядка в тылах, можно прыгнуть сразу туда где прервались и следовать по массиву далее.гномья сортировка
Так немного быстрее, хотя принципиально это временную сложность не улучшает, она как была так и остаётся O(n2). Но зато это приводит нас не только к новому способу сортировки, а даже к целому новому классу сортировок. И имя этой группе алгоритмов — Сортировки вставками.

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

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

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

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

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

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

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

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

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

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


Оставить комментарий