Структуры и алгоритмы обработки данных

· обход графа в глубину

· обход графа в ширину.

Требования к подпрограммам и главной программе - стандартные.

7.6 Контрольные вопросы

1. Какие проблемы возникают при использовании деревьев поиска?

2. Как влияет на структуру дерева поиска разный порядок поступления одних и тех же входных ключей?

3. Почему при построении дерева поиска важно управлять его структурой?

4. Какие деревья называются АВЛ-сбалансированными?

5. Как связаны понятия "идеально сбалансированное дерево" и "АВЛ-сбалансированное дерево"?

6. Приведите примеры идеально сбалансированного, АВЛ-сбалансированного и не-АВЛ-сбалансированного деревьев.

7. Какой параметр используется для реализации АВЛ-сбалансированных деревьев?

8. По какому алгоритму выполняется АВЛ-балансировка дерева при добавлении вершины?

9. Какие ситуации возможны при необходимости балансировки некоторого поддерева?

10. Как выполняется однократный поворот?

11. Как выполняется двукратный поворот?

12. Как выполняется балансировка дерева при удалении вершины?

13. Как описывается структура вершины дерева с дополнительными указателями на родителей?

14. Какие преимущества и недостатки имеют деревья с дополнительными указателями на родителей?

15. Для чего можно использовать деревья с дополнительными указателями на родителей?

16. В чем состоит основная сложность реализации недвоичных деревьев?

17. Какие списковые структуры можно использовать для реализации недвоичных деревьев?

18. Какую структуру должны иметь вершины недвоичных деревьев при реализации их с помощью списков?

19. Как реализуется вывод вершин недвоичного дерева, представленного с помощью списков?

20. Как реализуется добавление вершины в недвоичное дерево, представленное с помощью списков?

21. Как реализуется удаление вершины из недвоичного дерева, представленного с помощью списков?

22. Какие существуют разновидности графов?

23. Какие способы можно использовать для представления графов как структур данных?

24. Что такое матрица смежности и как она описывается?

25. Какие структуры данных необходимы для реализации списков смежности?

26. Какие основные задачи возникают при использовании графов?

27. Как реализуются операции добавления и удаления ребер в графе?

28. Как реализуются операции добавления и удаления вершин в графе?

29. Какие шаги включает в себя алгоритм поиска в глубину?

30. Какие шаги включает в себя алгоритм поиска в ширину?

Раздел 2. Алгоритмы сортировки и поиска

1. Классификация методов. Простейшие методы сортировки

1.1 Задача оценки и выбора алгоритмов

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

· точность решения задачи

· затраты машинного времени

· затраты оперативной памяти.

Как правило, перечисленные критерии противоречат друг другу, поэтому в каждой практической ситуации приходится выбирать наиболее важный критерий. В настоящее время, в связи с резким ростом объемов доступной оперативной памяти в большинстве случаев на первое место выходит временной критерий. Поскольку задача выбора алгоритмов возникает на этапе разработки программы, надо уметь оценивать алгоритмы по их трудоемкости еще до написания соответствующих программ. Для этого можно выделить в алгоритме наиболее часто повторяющиеся элементарные базовые операции и оценить зависимость числа их повторений от размерности обрабатываемых данных. Интуитивно понятно, что чем больше объем обрабатываемых данных, тем больше времени занимает эта обработка. Это связано с тем, что большинство алгоритмов в цикле повторяют одни и те же действия, и число повторов определяется объемом исходных данных. При этом часто разумно оценивать три величины:

· минимально возможное число повторов элементарных операций в наилучшем случае

· среднее число повторов

· максимальное число повторов для наихудшего случая.

Например, в задаче поиска в неупорядоченном массиве или списке из n элементов базовой операцией является сравнение заданного значения с ключом элемента массива. Тогда минимальное число сравнений равно 1 (совпадение произошло на первом элементе массива), максимальное равно n (просмотрен весь массив), а среднее - около n/2.

В отличие от этого, двоичный поиск в упорядоченном массиве или в "хорошем" двоичном дереве поиска дает другие оценки: минимум - 1, максимум - log ₂ n, среднее - 0,5* (log ₂ n).

Получение подобных оценок часто является сложной математической задачей. Наиболее полный анализ методов получения этих оценок для всех основных алгоритмов приводится в фундаментальной многотомной работе Дональда Кнута [1, 2].

В идеале каждый алгоритм должен оцениваться по всем 3 параметрам: наилучшему, наихудшему и среднему числу базовых операций. К сожалению, получение средних оценок часто бывает невозможно, и поэтому на практике больше всего используются оценки для наихудшего случая. При этом для сравнения алгоритмов важен не точный вид функциональной зависимости трудоемкости от объема входных данных, а скорее характер или поведение этой зависимости. Эта информация помогает ответить на следующий важнейший вопрос: если рост трудоемкости с увеличением объема данных неизбежен, то насколько быстро происходит этот рост?

Для оценивания трудоемкости алгоритмов была введена специальная система обозначений - так называемая О-нотация. Эта нотация позволяет учитывать в функции f (n) лишь наиболее значимые элементы, отбрасывая второстепенные.

Например, в функции f (n) = 2n² + n - 5 при достаточно больших n компонента n² будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида О(n²).

Аналогично, для функции f (n) = 2ⁿ + 3n^3-10 начиная с некоторого n первое слагаемое будет превосходить второе и поэтому данную функцию можно описать оценкой О(2ⁿ).

Важность О-оценивания состоит в том, что оно позволяет описывать характер поведения функции f(n) с ростом n: насколько быстро или медленно растет эта функция.

О-оценка позволяет разбить все основные функции на ряд групп в зависимости от скорости их роста:

1. постоянные функции типа О(1), которые с ростом n НЕ растут (в оценивании алгоритмов этот случай встречается крайне редко, но все-таки встречается!)

2. функции с логарифмической скоростью роста О(log ₂ n)

3. функции с линейной скоростью роста О(n)

4. функции с линейно-логарифмической скоростью роста О(n*log ₂ n)

5. функции с квадратичной скоростью роста О(n²)

6. функции со степенной скоростью роста О(n^a) при а>2

7. функции с показательной или экспоненциальной скоростью роста О(2ⁿ)

8. функции с факториальной степенью роста О(n!).

В этом списке функции упорядочены именно по критерию скорости роста: сначала идут медленно растущие функции, потом - все более быстро растущие. Графики некоторых функций приведены на рисунке.



Отсюда можно сделать несколько выводов.

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

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

3. Алгоритмы класса О(2ⁿ) и О(n!) следует использовать с большой осторожностью, учитывая катастрофический рост их трудоемкости уже при n>100. Например, если число базовых операций определяется соотношением 2ⁿ, то при n=100 это число будет примерно равно 10³⁰, и если одна базовая операция выполняется за 1 микросекунду, то это потребует около 10²⁴ секунд, т.е. порядка 10¹⁶ лет. К сожалению, задачи с подобной трудоемкостью довольно часто встречаются на практике и их точное решение пока невозможно даже на сверхбыстрых суперкомпьютерах!

Как быть с оценкой трудоемкости программы в целом, если в программе используется несколько алгоритмов, решающих свои конкретные задачи? Есть два основных способа взаимодействия алгоритмов - последовательное и вложенное. При последовательном выполнении алгоритмов с оценками O(f1), O(f2), …, O(fk) общая трудоемкость определяется трудоемкостью алгоритма с максимальным значением:

O (программы) = Max (O(f1), O(f2),..., O(fk))

При вложенном выполнении общая трудоемкость есть произведение оценок вложенных друг в друга алгоритмов: O(программы) = O(f1)*O(f2)*O(f3)

1.2 Классификация задач сортировки и поиска

Пусть задано некоторое множество элементов а ₁ а ₂, а ₃,..., а_n и требуется выстроить эти элементы по порядку в соответствии с заданной функцией предпочтения (например, по алфавиту). Очень часто значения функции предпочтения явно хранятся в исходных элементах в виде специального ключевого поля целого или строкового типа.

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

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

Все алгоритмы сортировки основаны на многократном повторении двух базовых операций: сравнение ключей у двух элементов и перестановка двух элементов. Подсчет именно этих операций лежит в основе методов оценивания трудоемкости алгоритмов сортировки.

Методы сортировки массивов можно разделить на две большие группы:

· Универсальные методы, не требующие никакой дополнительной информации об исходных данных и выполняющие сортировку "на месте", т.е. без использования больших объемов дополнительной памяти (например - для размещения копии исходного массива); такие методы в лучшем случае дают оценку трудоемкости порядка O(n*log ₂ n).

· Специальные методы, которые либо за счет некоторой дополнительной информации об исходных данных, либо за счет использования большой дополнительной памяти позволяют получить более высокую производительность сортировки порядка O(n) (примеры - карманная и поразрядная сортировка).

В свою очередь, универсальные методы сортировки делятся на две подгруппы:

· Простейшие методы с трудоемкостью порядка O(n²): сортировка обменом, сортировка выбором и сортировка вставками.

· Улучшенные методы с трудоемкостью O(n*log ₂ n): метод Шелла, пирамидальная сортировка, быстрая сортировка.

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

Общая классификация методов сортировки приводится на схеме. Описание всех методов приводится далее в пособии.

Аналогично можно провести классификацию методов поиска. Прежде всего - внутренний поиск и внешний поиск. Внутренний поиск - универсальный и специальный. Универсальный - поиск в упорядоченном или неупорядоченном наборе данных. Неупорядоченный набор - метод простого перебора (массив, список, иногда - дерево), упорядоченный - метод двоичного поиска в массиве или дереве. Специальный метод поиска в массиве (хеш-поиск) предполагает особую его организацию и используется при определенных ограничениях (правда, при выполнении этих ограничений данный метод дает потрясающую производительность - одно сравнение для поиска ЛЮБОГО элемента, независимо от объема входных данных!). Внешний поиск реализуется для сверхбольших объемов данных, которые нельзя одновременно разместить в основной памяти и требует использования внешних файлов (один из самых известных методов основан на использовании так называемых B-деревьев). Универсальные методы поиска были рассмотрены ранее, а остальные рассматриваются ниже, после описания методов сортировки.

1.3 Простейшие методы сортировки: метод обмена

Данный метод относится к классу простейших, занимая в нем последнее место по производительности. Тем не менее, он очень широко известен, видимо, благодаря своему одному легко запоминающемуся названию - метод всплывающего пузырька (или тонущего шарика, если кому-то так больше нравится). Работа алгоритма действительно похожа на всплывание наверх пузырьков воздуха: сначала на самый верх всплывает самый легкий элемент, потом за ним - чуть более тяжелый и т.д.

Пусть имеется n элементов а ₁ а ₂, а ₃,..., а_n, расположенных в ячейках массива. Для простоты будем считать, что сам элемент совпадает с его ключом. Алгоритм состоит в повторении n-1 шага, на каждом из которых в оставшемся необработанном наборе за счет попарного сравнения соседних элементов отыскивается минимальный элемент.

Шаг 1. Сравниваем а_n с а_n-1 и если а_n < а_n-1 то меняем их местами, потом сравниваем а_n-1 с а_n-2 и, возможно, переставляем их, сравниваем а_n-2 и а_n-3 и т.д. до сравнения и, возможно, перестановки а ₂ и а ₁. В результате на первом месте в массиве оказывается самый минимальный элемент, который в дальнейшей сортировке не участвует

Шаг 2. Аналогично сравниваем а_n с а_n-1, а_n-1 с а_n-2 и т.д., а ₃ с а ₂, в результате чего на месте а ₂ оказывается второй наименьший элемент, который вместе с а ₁ образует начальную часть упорядоченного массива

Шаг 3. Аналогичными сравнениями и перестановками среди элементов а ₃, а ₄, …, а_n находится наименьший, который занимает место а ₃ .....

Шаг n-1. К этому моменту первые n-2 элемента в массиве уже упорядочены и остается "навести порядок" только между двумя последними элементами а_n-1 и а_n. На этом сортировка заканчивается.

Пример. Дано 6 элементов - целые числа 15, 33, 42, 07, 12, 19.

Итого, для шести элементов сделано 5+4+3+2+1 = 15 сравнений и 8 перестановок.

В общем случае, на каждом из n-1 шагов выполняется в среднем n/2 сравнений, поэтому оценка для числа сравнений выражается соотношением n(n-1)/2, т.е. данный метод относится к классу O(n²). Аналогично, число перестановок тоже пропорционально n². Несмотря на то, что было предложено несколько улучшений данного метода (есть очень красивые названия - например, шейкер-сортировка), он остается самым неэффективным. Уже для 1000 элементов число сравнений выражается внушительной величиной порядка 500 тысяч.

Программная реализация включает двойной цикл: внешний реализует основные шаги алгоритма, внутренний сравнивает и переставляет элементы, начиная с конца массива.

for i:= 2 to n do

begin

for j:= n downto i do

if a [j-1]> a [j]then

begin temp:= a [j-1]; a [j-1]:= a [j]; a [j]:= temp; end;

end;

1.4 Простейшие методы сортировки: метод вставок

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

Пусть имеется n элементов а ₁ а ₂, а ₃,..., а_n, расположенных в ячейках массива. Сортировка выполняется за (n-1) шаг, причем шаги удобно нумеровать от 2 до n. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

· левую часть образуют уже упорядоченные на предыдущих шагах элементы а ₁, а ₂, а ₃,..., а_i-1

· правую часть образуют еще не обработанные элементы а_i, а_i+1, а_i+2,..., а_n.

На шаге i для элемента а_i находится подходящее место в уже отсортированной последовательности. Поиск подходящего места выполняется поэлементными сравнениями и перестановками по необходимости: сравниваем а_i с а_i-1, если а_i < а_i-1, то переставляем их, потом сравниваем а_i-1 с а_i-2 и т. д. Сравнения и, возможно, перестановки продолжаются до тех пор, пока не будет выполнено одно из 2-х следующих условий:

· в отсортированном наборе найден элемент, меньший а_i (все остальные не просмотренные элементы будут еще меньше)

· достигнут первый элемент набора а ₁, что произойдет в том случае, если а_i меньше всех элементов в отсортированном наборе и он должен занять первое место в массиве

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

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

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

for i:= 2 to n do

begin

temp:= a [i]; j:= i - 1;

While (j > 0) and (temp < a [j]) do

begin a [j+1]:= a [j]; j:= j - 1; end;

a [j+1]:= temp;

end;

1.5 Простейшие методы сортировки: метод выбора

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

Пусть имеется n элементов а ₁ а ₂, а ₃,..., а_n, расположенных в ячейках массива. Сортировка выполняется за (n-1) шаг, пронумерованных от 1 до n-1. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

· левую часть образуют уже упорядоченные на предыдущих шагах элементы а ₁, а ₂, а ₃,..., а_i-1

· правую часть образуют еще не обработанные элементы а_i, а_i+1, а_i+2,..., а_n.

Суть метода состоит в том, что в необработанном наборе отыскивается наименьший элемент, который меняется местами с элементом а_i. На первом шаге (при i = 1), когда необработанным является весь исходный набор, это сводится к поиску наименьшего элемента в массиве и обмену его с первым элементом. Ясно, что поиск наименьшего элемента выполняется обычным попарным сравнением, но соседние элементы при этом не переставляются, что в целом уменьшает число пересылок.

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

В данном примере сделано 15 сравнений (как и в методе пузырька), но всего 4 перестановки. Эта особенность сохраняется и в целом: по числу сравнений метод выбора близок к методу пузырька, но по числу перестановок существенно превосходит оба рассмотренные выше методы (оценка числа перестановок n*log ₂ n).

Особенности программной реализации. Внешний цикл обрабатывает основные шаги и выполняет перестановку минимального элемента, а внутренний организует поиск наименьшего элемента в необработанной части массива:

for i:= 1 to n-1 do

begin

k:= i; temp:= a [i]; {устанавливаем начальный минимальный элемент}

for j:= i+1 to n do

if a [j]< temp then

begin {изменяем текущий минимальный элемент}

k:= j; temp:= a [j];

end;

a [k]:= a [i]; a [i]:= temp;

end;

Общее заключение по простейшим методам сортировки.

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

Метод вставок также дает хорошие результаты для упорядоченных входных данных (число сравнений и пересылок пропорционально n). Во всех остальных случаях его показатели пропорциональны n², хотя что касается оценки среднего числа сравнений, то она чуть лучше, чем у других методов. Многочисленные эксперименты показывают, что метод вставок дает наименьшее время сортировки среди всех простейших методов.

Метод выбора, как это и следовало ожидать, имеет лучшие показатели по числу пересылок, особенно - для общего случая, где оценка О(n*log ₂ n) заметно лучше оценки O(n²). Поэтому его можно рекомендовать к использованию из всех простейших методов в том случае, если именно число перестановок является наиболее важным.

1.6 Практическое задание

Реализовать программу, объединяющую простейшие методы сортировки массивов:

· сортировку обменом (метод пузырька)

· сортировку выбором

· сортировку вставками.

Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Кроме того, необходима вспомогательная подпрограмма генерации исходного массива случайных целых чисел с заданным числом элементов (не более 10 000) и выводом этого массива на экран.

Каждый исходный массив должен обрабатываться всеми подпрограммами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. Поскольку каждый из универсальных методов выполняет сортировку "на месте", т.е. изменяет исходный массив, то для наглядности работы можно передавать в подпрограмму сортировки копию исходного массива, объявив его как параметр-значение.

После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1.000, 10.000) и провести сравнительный анализ эффективности рассматриваемых методов.

Главная программа должна реализовать диалог с пользователем для выбора метода сортировки.

1.7 Контрольные вопросы

1. В чем состоит задача выбора алгоритмов решения однотипных задач?

2. Какие критерии используются при выборе алгоритмов?

3. Как оценивается трудоемкость алгоритма?

4. Что такое О-нотация и для чего она используется?

5. Какие группы функций можно выделить с помощью О-нотации?

6. Какие рекомендации следует использовать при выборе алгоритмов с помощью О-нотации?

7. Что можно сказать о применимости алгоритмов класса О(2ⁿ) и О(n!)?

8. Как оценивается трудоемкость программы, использующей несколько взаимодействующих алгоритмов?

9. Как классифицируются методы сортировки?

10. Что такое внутренняя и внешняя сортировка и в чем состоят особенности этих задач?

11. В чем состоят особенности универсальных и специальных методов внутренней сортировки?

12. Какие основные методы сортировки относятся к универсальным и какую они имеют трудоемкость?

13. В чем состоит практическое значение изучения простейших методов сортировки?

14. Как классифицируются методы поиска?

15. В чем состоит суть метода сортировки обменом?

16. Какие шаги выполняет алгоритм сортировки обменом?

17. Как программно реализуется сортировка обменом?

18. В чем достоинства и недостатки метода сортировки обменом?

19. Приведите практический пример сортировки массива методом обмена.

20. В чем состоит суть метода сортировки вставками?

21. Какие шаги выполняет алгоритм сортировки вставками?

22. Как программно реализуется сортировка вставками?

23. В чем достоинства и недостатки метода сортировки вставками?

24. Приведите практический пример сортировки массива методом вставок.

25. В чем состоит суть метода сортировки выбором?

26. Какие шаги выполняет алгоритм сортировки выбором?

27. Как программно реализуется сортировка выбором?

28. В чем достоинства и недостатки метода сортировки выбором?

29. Приведите практический пример сортировки массива методом выбора.

2. Улучшенные методы сортировки массивов

2.1 Метод Шелла

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

Алгоритм метода Шелла состоит в многократном повторении двух основных действий:

· объединение нескольких элементов исходного массива по некоторому правилу

· сортировка этих элементов обычным методом вставок.

Более подробно, на первом этапе группируются элементы входного набора с достаточно большим шагом. Например, выбираются все 1000-е элементы, т.е. создаются группы:

группа 1: 1, 1001, 2001, 3001 и т.д.

группа 2: 2, 1002, 2002, 3002 и т.д.

группа 3: 3, 1003, 2003, 3003 и т.д.

.....................

группа 1000: 1000, 2000, 3000 и т.д.

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

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

На третьем этапе элементы группируются с еще меньшим шагом, например - все десятые элементы. Выполняется сортировка, группировка с еще меньшим шагом и т.д.

На последнем этапе сначала выполняется группировка с шагом 1, создающая единственный набор данных размерности n, а затем - сортировка практически отсортированного набора.

Пример. Исходный набор: 15-33-42-07-12-19

Выполняем группировку с шагом 3, создаем три группы по 2 элемента и сортируем каждую из них отдельно:

группа 1: 15-07 => 07-15 (1 сравнение, 1 пересылка)

группа 2: 33-12 => 12-33 (1 сравнение, 1 пересылка)

группа 3: 42-19 => 19-42 (1 сравнение, 1 пересылка)

Новый набор чисел: 07-15-12-33-19-42

Группировка с меньшим шагом 2 дает 2 группы по 3 элемента, которые сортируются отдельно:

группа 1: 07-12-19 => уже упорядочена (2 сравнения, 0 пересылок)

группа 2: 15-33-42 => уже упорядочена (2 сравнения, 0 пересылок)

Новый набор чисел: 07-12-19-15-33-42

Последняя группировка с шагом 1 дает сам набор чисел; к нему применяется сортировка вставками с 5-ю сравнениями и только одной пересылкой, после чего получаем искомый результат.

Итого - 12 сравнений и 4 пересылки, что в общем-то не лучше, чем у простых методов. Однако, здесь надо учесть два фактора.

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

Фактор 2 (специфический). Эффективность метода Шелла существенно зависит от выбора последовательности шагов группировки. Эта последовательность обязательно должна быть убывающей, а последний шаг обязательно равен 1. В настоящее время неизвестна наилучшая последовательность шагов, обеспечивающая наименьшую трудоемкость. На основе многочисленных экспериментов установлено, что число шагов группировки надо выбирать по формуле [(log ₂ n)]- 1, где скобки [] используются для обозначения целой части числа, а в качестве самих последовательностей рекомендуется один из следующих наборов (обращаю внимание: для удобства восприятия шаги даются в обратном порядке):

1, 3, 5, 9, 17, 33, ... (общая формула: t_k = (2* t_k-1) - 1)

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767... (общая формула: t_k = (2* t_k-1) +1, а еще проще - (2^k - 1)).

В соответствии с этими рекомендациями, в предыдущем примере надо взять лишь 2 шага группировки со значениями 3 и 1. В этом случае потребуется лишь 8 сравнений и 5 пересылок.

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

for m:= 1 to t do {t - число шагов группировки, m - номер шага}

begin

k:= h [m]; {выбор величины шага группировки из заданного массива}

for i:= k + 1 to n do {сортировка вставками внутри каждой группы}

begin

temp:= a [i]; j:= i - k;

while (j > 0) and (temp < a [j]) do

begin

a [j + k]:= a [j]; j:= j - k;

end;

a [j + k]:= temp;

end;

end;

Оценка трудоемкости метода Шелла выражается соотношением O(n^1,2), что лучше, чем у простейших методов, особенно при больших n.

2.2 Метод быстрой сортировки

Данный метод в настоящее время считается наиболее быстрым универсальным методом сортировки. Как ни странно, он является обобщением самого плохого из простейших методов - обменного метода. Эффективность метода достигается тем, что перестановка применяется не для соседних элементов, а отстоящих друг от друга на приличном расстоянии.

Более конкретно, алгоритм быстрой сортировки заключается в следующем.

· пусть каким-то образом в исходном наборе выделен некий элемент x, который принято называть опорным. В простейшем случае в качестве опорного можно взять серединный элемент массива

· просматривается часть массива, расположенная левее опорного элемента и находится первый по порядку элемент a_i > x

· после этого просматривается часть массива, расположенная правее опорного элемента, причем - в обратном порядке, и находится первый по порядку (с конца) элемент a_j < x

· производится перестановка элементов a_i и a_j

· после этого в левой части, начиная с a_i отыскивается еще один элемент, больший x, а в правой части, начиная с a_j отыскивается элемент, меньший х

· эти два элемента меняются местами

· эти действия (поиск слева и справа с последующим обменом) продолжаются до тех пор, пока не будет достигнут опорный элемент x

· после этого слева от опорного элемента x будут находиться элементы, меньшие опорного, а справа - элементы, большие опорного. При этом обе половины скорее всего не будут отсортированными

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

Пример. Пусть исходный набор включает 11 чисел: 13-42-28-17-09-25-47-31-39-15-20. Основные шаги сортировки:

1. Выбор серединного элемента 25 (индекс 6): 13 42 28 17 09 25 47 31 39 15 20

2. поиск слева первого элемента, большего 25: 42 (2 сравнения)

3. поиск справа от конца первого элемента, меньшего 25: 20 (1 сравнение)

4. перестановка элементов 42 и 20: 13 20 28 17 09 25 47 31 39 15 42

5. поиск слева от 25 еще одного элемента, большего 25: 28 (1 сравнение)

6. поиск справа от 25 еще одного элемента, меньшего 25: 15 (1 сравнение)

7. перестановка элементов 28 и 15: 13 20 15 17 09 25 47 31 39 28 42

8. поиск слева от 25 еще одного элемента, большего 25: нет (2 сравнения)

9. поиск справа от 25 еще одного элемента, меньшего 25: нет (3 сравнения)

10. теперь слева от 25 все элементы меньше 25, а справа - больше

11. выделяем отдельно левую часть: 13 20 15 17 09

12. выбираем серединный элемент 15 (индекс 3): 13 20 15 17 09

13. поиск слева от 15 элемента, большего 15: 20 (2 сравнения)

14. поиск справа от 15 элемента, меньшего 15: 09 (1 сравнение)

15. перестановка 20 и 09: 13 09 15 17 20

16. поиск справа от 15 еще одного элемента, меньшего 15: нет (1 сравнение)

17. теперь слева от 15 все элементы меньше 15, а справа - больше

18. поскольку слева от 15 только 2 элемента, просто сравниваем их друг с другом и переставляем (09 и 13)

19. поскольку справа от 15 только 2 элемента, просто сравниваем их и не переставляем

20. получаем для левой части упорядоченный набор: 09 13 15 17 20

21. возвращаемся к правой части: 47 31 39 28 42

22. выделяем серединный элемент 39 (индекс в данном поднаборе - 3): 47 31 39 28 42

23. поиск слева от 39 элемента, большего 39: 47 (1 сравнение)

24. поиск справа от 39 элемента, меньшего 39: 28 (2 сравнения)

25. переставляем 47 и 28: 28 31 39 47 42

26. поиск слева от 39 еще одного элемента, большего 39: нет (1 сравнение)

27. теперь слева от 39 все элементы меньше 39, а справа - больше

28. поскольку слева от 39 только 2 элемента, просто сравниваем их и не переставляем

29. поскольку справа от 39 только 2 элемента, просто сравниваем их и переставляем (42 и 47)

30. получаем для правой части упорядоченный набор: 28 31 39 42 47

31. вместе с левой частью и серединным элементом 25 получаем окончательный результат.

Итого для данного примера потребовалось 22 сравнения и 6 пересылок.

В целом, оценка трудоемкости метода быстрой сортировки является типичной для улучшенных методов и выражается соотношением (n*log ₂ n)/6. Отсюда следует, что данный метод неэффективен при малых n (десятки или сотни элементов), но с ростом n его эффективность резко растет, и при очень больших n метод дает наилучшие показатели среди всех универсальных методов сортировки.

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

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

На практике хорошо показал себя следующий способ: выбрать случайно в массиве три элемента и взять в качестве опорного средний из них. Этот способ очень прост в реализации, т.к. требует только двух сравнений, но, конечно, он может обеспечивать хорошие показатели только в среднем, и не гарантирует идеальное поведение алгоритма абсолютно для ЛЮБЫХ входных данных.

Есть и другие усовершенствования базового алгоритма быстрой сортировки. Среди них:

· Проверка каждого подмассива на возможную упорядоченность перед самой сортировкой

· Для малых подмассивов (n<10) разумно проводить сортировку с помощью более простых методов, например - Шелла.

Комбинация всех этих методов известна как метод Синглтона [7].

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

Рекурсивная реализация с серединным опорным элементом схематично выглядит следующим образом:

Procedure QuickSort (left, right: integer);

{формальные параметры для запоминания границ}

var i, j: integer;

sred, temp: <описание элемента исходного массива>;

begin

i:= left; j:= right; {установка начальных значений границ подмассива}

sred:= mas [(left + right) div 2]; {определение серединного элемента}

repeat

while (mas [i]< sred) do i:= i + 1;

{поиск слева элемента, большего опорного}

while (mas [j]> sred) do j:= j - 1;

{поиск справа элемента, меньшего опорного}

if i <= j then

begin {обмениваем элементы и изменяем индексы}

temp:= mas [i]; mas [i]:= mas [j]; mas [j]:= temp;

i:= i + 1; j:= j - 1;

end;

until i > j;

if left < j then QuickSort (left, j); {обработка левой половины}

if i < right then QuickSort (i, right); {обработка правой половины}

end;

Первоначальный вызов этой процедуры производится в главной программе в виде QuickSort (1, n); здесь n - число элементов в массиве.

2.3 Пирамидальная сортировка

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

Пусть имеется исходный массив n элементов а ₁ а ₂, а ₃,..., а_n. Расположим эти элементы в виде двоичного дерева следующего вида (здесь важен порядок следования индексов элементов):



Подобное дерево называется пирамидой, если для всех элементов с индексами от 1 до n/2 выполняются следующие условия:

а_i <= а_2i и а_i <= а _2i+1

В частности, эти условия означают: а ₁ <= а ₂ и а ₁ <= а ₃; а ₂ <= а ₄ и а ₂ <= а ₅; а ₃ <= а ₆ и а ₃ <= а ₇; а ₄ <= а ₈ и а ₄ <= а ₉, и т.д.

Другими словами, в каждом элементарном поддереве значение в вершине этого поддерева меньше или равно значений в вершинах-потомках.

Пример двоичного дерева-пирамиды с 15-ю элементами:

Такие пирамиды иногда называют минимальными, в отличие от максимальных, где правило упорядоченности прямо противоположное.

Из примера видно, что пирамида НЕ является деревом поиска, т.к. строится по другим правилам.

Можно отметить следующие полезные свойства пирамиды:

· на вершине пирамиды всегда находится наименьший элемент во всем массиве (элемент а ₁), элемент а ₂ является наименьшим для левого поддерева, элемент а ₃ является наименьшим для правого поддерева и т.д.

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

Пирамидальная сортировка включает два больших этапа:

· представление исходного массива в виде пирамиды

· последовательные удаления минимального элемента с вершины пирамиды с заменой его другим элементом.

Реализация 1 этапа включает следующие шаги:

· условно разделяем исходный массив на две половины: левую с индексами от 1 до [n/2], и правую с индексами от [n/2]+1 до n (здесь []обозначает целую часть); считаем пока, что левая половина образует верхнюю часть строящейся пирамиды, а правая - нижний слой терминальных вершин

· выбираем в левой половине последний элемент (его индекс m= [n/2]), а в правой половине - его непосредственных потомков (одного или двух, но хотя бы один будет обязательно) с индексом 2m и, возможно, 2m+1

· если потомков два, то выбираем из них наименьшего

· сравниваем элемент а_m с наименьшим из потомков: если он больше, то меняем эти элементы в массиве местами для получения фрагмента пирамиды; в противном случае оставляем все без изменений, поскольку эти элементы уже образуют фрагмент пирамиды

· повторяем все описанные действия последовательно для оставшихся в левой части элементов справа налево, т.е. для а_m-1, а_m-2, а_m-3,..., а ₁, при этом если происходит обмен между родительской вершиной и одним из потомков, выполняется проверка для новой вершины-потомка, т.к. она может иметь своих потомков, с которыми возможно потребуется ее обменять для выполнения условия пирамиды.

Тем самым, для каждого элемента массива находится его новое расположение в массиве таким образом, чтобы выполнялись условия пирамиды. Процесс определения нужного положения элемента в массиве-пирамиде называют просеиванием элемента через пирамиду. Построение пирамиды заканчивается после просеивания первого элемента а ₁. Пример для 15 элементов приведен в таблице (символ ~ обозначает перестановку элементов)

В худшем случае каждый шаг в просеивании очередного элемента требует двух сравнений: сначала сравниваются два потомка текущего элемента, а потом наименьший из них сравнивается с самим элементом. В примере для построения пирамиды потребовалось 11*2=22 сравнения и 9 пересылок.

Реализация второго этапа состоит в (n-1)-кратном повторении следующих действий:

· с вершины пирамиды забирается минимальный элемент а ₁

· на его место в вершину пирамиды помещается последний элемент в массиве, причем индекс этого последнего элемента на каждом шаге будет уменьшаться от а_n до а ₂

· помещенный в вершину элемент просеивается через пирамиду обычным образом, при этом он встает на свое место, а в вершину пирамиды выталкивается минимальный из оставшихся в массиве элементов

· на последнем шаге в пирамиде останется один элемент (самый большой) и сортировка будет закончена.

При этом возникает вопрос - куда девать снимаемые с вершины пирамиды элементы? Можно просто помещать их в конец массива на место элемента, размещаемого в вершине. В результате на месте исходного массива создается упорядоченный ПО УБЫВАНИЮ набор данных. При необходимости, алгоритм легко можно изменить для получения возрастающих последовательностей, если вместо минимальных использовать максимальные пирамиды.

В данном примере выполнено 51 сравнение и 40 пересылок, что вместе с этапом построения пирамиды дает 73 сравнения и 49 пересылок.

В целом, данный метод с точки зрения трудоемкости имеет типичное для улучшенных методов поведение: довольно высокая трудоемкость для небольших n, но с ростом n эффективность метода растет. При больших n метод в среднем немного уступает быстрой сортировке и имеет оценку порядка (n*log ₂ n)/2. Единственное, в чем он превосходит быструю сортировку, так это поведение на аномальных входных данных, когда быстрая сортировка перестает быть "быстрой", а пирамидальная сохраняет свою трудоемкость порядка O(n*log ₂ n).

В [4] указывается, что пирамидальную сортировку выгодно использовать в том случае, когда требуется не провести полную сортировку большого набора данных, а лишь найти несколько (причем - немного) первых наименьших элементов.

Необходимо отметить, что понятие пирамидального дерева имеет и самостоятельное значение, и часто используется для решения других задач, не связанных с сортировкой массивов, например - для эффективной реализации приоритетных очередей [4].



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

Procedure Sito (al, ar: word);

var i, j: word;

x: <описание элемента массива>;

begin

i:= al; j:= 2*al; x:= mas [al];

if (j < ar) and (mas [j + 1]< mas [j]) then j:= j + 1;

while (j <=ar) and (mas [j]< x) do

begin

mas [i]:= mas [j]; i:=j; j:=2*j;

if (j < ar) and (mas [j + 1]< mas [j]) then j:= j + 1;

end;

mas [i]:= x;

end;

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

left:= (n div 2) + 1; right:= n;

{определение границ правой половины массива}

while left > 1 do

begin {цикл построения пирамиды}

left:= left - 1; Sito (left, right);

end;

while right > 1 do (цикл сортировки}

begin

temp:= mas [1]; mas [1]:= mas [right]; mas [right]:= temp;

right:= right - 1; Sito (left, right);

end;

2.4 Практическое задание

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

Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Каждый исходный массив должен обрабатываться всеми программами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1.000, 10.000) и провести сравнительный анализ эффективности рассматриваемых методов.

Главная программа должна реализовать диалог с пользователем для выбора метода сортировки.

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

2.5 Контрольные вопросы

1. В чем состоит суть сортировки методом Шелла?

2. За счет чего метод Шелла дает лучшие показатели по сравнению с простейшими методами?

3. Приведите практический пример сортировки массива методом Шелла.

4. Какой фактор оказывает наибольшее влияние на эффективность сортировки методом Шелла?

5. Какие последовательности шагов группировки рекомендуются для практического использования в методе Шелла?

6. Как программно реализуется сортировка методом Шелла?

7. В чем состоит суть метода быстрой сортировки?

8. За счет чего метод быстрой сортировки дает лучшие показатели по сравнению с простейшими методами?

9. Что такое опорный элемент в методе быстрой сортировки и как он используется?

10. Приведите практический пример быстрой сортировки массива.

11. Что можно сказать о применимости метода быстрой сортировки с точки зрения его эффективности?

12. Какой фактор оказывает решающее влияние на эффективность метода быстрой сортировки?

13. Почему выбор серединного элемента в качестве опорного в методе быстрой сортировки может резко ухудшать эффективность метода?

14. Какое правило выбора опорного элемента в методе быстрой сортировки является наилучшим и почему его сложно использовать?

15. Какое простое правило выбора опорного элемента в методе быстрой сортировки рекомендуется использовать на практике?

16. Какие усовершенствования имеет базовый алгоритм метода быстрой сортировки?

...