Алгоритм сортировки методом Шелла




Скачать 22.89 Kb.
НазваниеАлгоритм сортировки методом Шелла
Дата публикации13.04.2013
Размер22.89 Kb.
ТипДокументы
Алгоритм сортировки методом Шелла
Сортировку Шелла придумал Дональд Л. Шелл. Ее необычность состоит в том, что она рассматривает весь список как совокупность перемешанных подсписков. На первом шаге эти подсписки представляют собой просто пары элементов. На втором шаге в каждой группе по четыре элемента. При повторении процесса число элементов в каждом подсписке увеличивается, а число подсписков, соответственно, падает. На рисунке ниже изображены подсписки, которыми можно воспользоваться при сортировке списка из 16 элементов.



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

Сортировка подсписков выполняется путем однократного применения сортировки вставками. (Сортировка вставками

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

Вот алгоритм, реализующий этот процесс:

InsertionSort(list, N)

list сортирующий список элементов

N число элементов в списке

for i = 2 to N do

newElement = list[i]

location = i - 1

while (location >= 1) and (list[location] > newElement) do

//сдвигаем все элементы, большие очередного

list[location + 1] = list[location]

location = location - 1

end while

list[location + 1] = newElement

end for

Этот алгоритм заносит новое вставляемое значение в переменную newElement. Затем он освобождает место для этого нового элемента, подвигая (в цикле while) все большие элементы на одну позицию в массиве. Последняя итерация цикла переносит элемент с номером location + 1 в позицию location + 2. Это означает, что позиция location + 1 освобождается для "нового" элемента.)

В результате мы получаем следующий алгоритм:

ShellSort(list, N)

list сортируемый список элементов

N число элементов в списке
passes = [log_2 N]

while (passes >= 1) do

increment = 2^passes-1

for start = 1 to increment do

InsertionSort(list, N, start, increment)

end for

passes = passes - 1

end while

Переменная increment содержит величину шага между номерами элементов подсписка. (На рисунке шаг принимает значения 8, 4, 2 и 1.) В алгоритме мы начинаем с шага, на 1 меньшего наибольшей степени двойки, меньшей, чем длина списка. Поэтому для списка из 1000 элементов первое значения шага равно 511. Значение шага также равно числу подсписков. Элементы первого подсписка имеют номера 1 и 1 + increment; первым элементов последнего подсписка служит элемент с номером increment.

При последнем исполнении цикла while значение переменной passes будет равно 1, поэтому при последнем вызове функции InsertionSort значение переменной будет равно 1.

Добавить документ в свой блог или на сайт

Похожие:

Алгоритм сортировки методом Шелла iconАлгоритм быстрой сортировки
В первую часть попадают все элементы, меньшие выбранного, а во вторую большие элементы. В среднем такая сортировка эффективна, однако...

Алгоритм сортировки методом Шелла iconПрограмма оценки устойчивости склонов мезорельефа на подрабатываемых...
Описані алгоритм І програма розрахунку коефіцієнта запасу стійкості для схилу мезорельєфу методом стійкого укосу та методом кругло-циліндричних...

Алгоритм сортировки методом Шелла icon1, К. Вессон 2 1 Институт глобальных проблем нан украины
Описан алгоритм решения глобальных проблем методом случайных чисел. Проведены сравнения предложенного метода с трансцендентными вариантами...

Алгоритм сортировки методом Шелла iconАлгоритм пирамидальной сортировки
Пирамида представляет собой дерево, в котором каждый узел имеет не более двух потомков, причем узел всегда больше или равен своим...

Алгоритм сортировки методом Шелла iconМетоды сортировки
Поэтому можно сказать, что достаточно четкие представления об этой области нужны при решении любой задачи на ЭВМ как обязательные...

Алгоритм сортировки методом Шелла iconАлгоритм Флойда Уоршелла Алгоритм Флойда Уоршелла 
Алгоритм Флойда Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного...

Алгоритм сортировки методом Шелла iconДомашнее задание 6 Лабораторная работа Рекурсия и ее применение....
Лабораторная работа Простейшие алгоритмы сортировок (сортировка методом пузырька, вставки, выборки) 5

Алгоритм сортировки методом Шелла iconПрактическая работа 1 Тема: Решение нелинейных уравнений
Цель работы: Научиться находить корни уравнения методами: половинного деления, методом простой итерации, методом Ньютона, методом...

Алгоритм сортировки методом Шелла iconЗакон трихотомии
Они, как правило, входят в набор данных, который называется записью. Каждая запись содержит ключ, являющийся сортируемым значением,...

Алгоритм сортировки методом Шелла iconРешить систему линейных уравнений методом Крамера, методом Гаусса, матричным методом
Даны точки в полярной системе координат А(1; 1) и В(2;2). Найти расстояние между ними

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<