Алгоритм сортировки методом Шелла
Скачать 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. |
Добавить документ в свой блог или на сайт
Похожие:
 | В первую часть попадают все элементы, меньшие выбранного, а во вторую большие элементы. В среднем такая сортировка эффективна, однако... | | Описані алгоритм І програма розрахунку коефіцієнта запасу стійкості для схилу мезорельєфу методом стійкого укосу та методом кругло-циліндричних... |
| Описан алгоритм решения глобальных проблем методом случайных чисел. Проведены сравнения предложенного метода с трансцендентными вариантами... | | Пирамида представляет собой дерево, в котором каждый узел имеет не более двух потомков, причем узел всегда больше или равен своим... |
| Поэтому можно сказать, что достаточно четкие представления об этой области нужны при решении любой задачи на ЭВМ как обязательные... | | Алгоритм Флойда Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного... |
| Лабораторная работа Простейшие алгоритмы сортировок (сортировка методом пузырька, вставки, выборки) 5 | | Цель работы: Научиться находить корни уравнения методами: половинного деления, методом простой итерации, методом Ньютона, методом... |
| Они, как правило, входят в набор данных, который называется записью. Каждая запись содержит ключ, являющийся сортируемым значением,... | | Даны точки в полярной системе координат А(1; 1) и В(2;2). Найти расстояние между ними |