Сортировка шелла алгоритм блок схема

Сортировка шелла алгоритм блок схема

Дата добавления: 2013-12-23 ; просмотров: 4955 ; Нарушение авторских прав

Блок-схема быстрой сортировки

Пример работы быстрой сортировки

Имеется массив данных: 34, 17, 45, 9, 6, 18, 12, 14, 37, 49, 5. Его необходимо отсортировать по возрастанию (табл. 13.1). Разобьём для этого массив на две части и выберем элемент x равный 18. Выберем из левой части первый элемент, который больше 18 – это 34, а из правой части элемент, который меньше 18 – это 5. Поменяем их местами и получим новую последовательность: 5, 17, 45, 9, 6, 18, 12, 14, 37, 49, 34. Далее процесс повторяется (см. Таблицу 13.1).

Пример работы быстрой сортировки на примере

Шаг Последовательность элементов X Меняем
34, 17, 45, 9, 6, 18, 12, 14, 37, 49, 5 34 и 5
5, 17, 45, 9, 6, 18, 12, 14, 37, 49, 34 45 и 14
5, 17, 14, 9, 6, 18, 12, 45, 37, 49, 34
5, 17, 14, 9, 6, 12, 18, 45, 37, 49, 34 17 и 12
5, 12, 14, 9, 6, 17, 18, 45, 37, 49, 34
5, 12, 6, 14, 9, 17, 18, 45, 37, 49, 34
5, 12, 6, 9, 14, 17, 18, 45, 37, 49, 34
5, 9, 12, 6, 14, 17, 18, 45, 37, 49, 34
5, 9, 6, 12, 14, 17, 18, 45, 37, 49, 34
5, 6, 9, 12, 14, 17, 18, 45, 37, 49, 34 5, 37 -, 45 и 34
5, 6, 9, 12, 14, 17, 18, 34, 37, 49, 45
5, 6, 9, 12, 14, 17, 18, 34, 37, 45, 49

Если индекс выбранного x равен i, то он делит массив сначала на две части: 1) a[1]. a[i-1] и 2) a[j+1]. a[n], где j = i+1 для текущего случая. Потом разделение аналогичным образом повторяется. Описанные ниже блок-схемами алгоритмы просты и эффективны, так как сравниваемые переменные i, j и x можно хранить во время просмотра в быстрых регистрах процессора. Здесь применяется процесс разделения к получившимся двум частям, затем к частям частей, и так далее до тех пор, пока каждая из частей не будет состоять из одного единственного элемента. Процедура sort реализует разделение массива на две части, и рекурсивно обращается сама к себе (рис. 13.1). Данная процедура sort(m,l) описывается и вызывается в процедуре hoarsort (рис. 13.2), которая потом вызывается в программе таким образом: hoarsort(b, n), где b – это отсортированный массив, а – это число элементов в массиве.

Существуют и другие способы реализации процедуры sort(m,l), которые могут значительно сократить код программы и уменьшить число используемых переменных.

Улучшенные методы сортировки. Сортировка шелла. Её эффективность.

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

Принцип работы сортировки шелла и необходимые расчёты для её реализации

Читайте также:  Кто отписался в инстаграме приложение на андроид

Необходимо на каждом шаге произвести определённые действия, если t – это переменная, которая хранит номер этого шага. Сначала определяются все подпоследовательности, в которых расстояния между элементами равно kt. Далее каждая из этих подпоследовательностей сортируется методом прямого включения.

Сложным и важным местом данного алгоритма является нахождение убывающей последовательности расстояний kt, kt-1. , k1. Она должна обладать определёнными свойствами:

1) k1 = 1;

2) kt > kt-1для всех t;

3) kt не должны быть кратными друг другу (это для того, чтобы не повторялась обработка ранее отсортированных элементов).

Дональд кнут предложил две последовательности расстояний:

1) 1, 4, 13, 40, 121, …, т.е. Kt = 1+3*kt-1;

2) 1, 3, 7, 15, 31, …, т.е. Kt = 1+2*kt-1 = 2 t — 1.

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

Пример расчёта последовательности расстояний для малых массивов

Для удачного подбора значений необходимо, чтобы длина массива n попадала в такие границы

Kt t t+1 . (14.1).

Если прологарифмировать (14.1) по основанию 2, то можно получить следующее уравнение:

T t -1 или k= (1 shl t)-1. (14.6)

Количество подпоследовательностей, которые необходимо будет отсортировать прямой вставкой, для рассматриваемого шага будет равна k.

Далее необходимо определить, сколько элементов будет входить в каждую подпоследовательность. Если длину всей сортируемой последовательности n можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно

S = n div k. (14.7)

Если же n не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на единицу. Количество таких подпоследовательностей равно остатку от деления n на шаг k:

В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.

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

Первое значение, соответствующее расстоянию d равно 10/2=5. На каждом шаге оно уменьшается вдвое. Элементы, входящие в одну группу, сравниваются и если значение какого-либо элемента, стоящего левее того с которым он сравнивается, оказывается больше (сортировка по возрастанию), тогда они меняются местами. Так, элементы путем внутригрупповых перестановок постепенно становятся на свои позиции, и на последнем шаге (d=1) сортировка сводится к проходу по одной группе, включающей в себя все N элементов массива. При этом число требуемых обменов оказывается совсем небольшим.

Читайте также:  Планшет самсунг галакси ноте 8000


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

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

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

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

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

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

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

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

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

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

Читайте также:  Для чего нужна азбука морзе

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

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

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

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

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

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

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

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

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

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

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

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

Ссылка на основную публикацию
Соевый соус стебель бамбука классический отзывы
Всем доброго дня!Много мнений по этому поводу, как вы считаете, соевый соус или морская соль, что менее вредно для организма....
Сколько секунд видео можно загрузить в инстаграм
Обновлено - 27 января 2020 IGTV — функция, с помощью которой можно выложить длинное видео в Инстаграм продолжительностью от 15...
Сколько символов на странице ворд
Вы можете посмотреть пример стандартной страницы перевода в формате doc. В рынке переводов можно встретить разные варианты определения условной страницы:...
Соевый соус ямаса отзывы
Полное наименование: Соевый Соус классический (натурально сваренный) Изготовитель: Yamasa Corporation Все характеристики Соевый соус Yamasa: Результаты теста Достоинства Безопасный Не...
Adblock detector