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

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

Формулировка задачи может быть записана следующим образом.

Если даны элементы а₁, а₂ ,…, а_n, то сортировка означает перестановку этих элементов в массив а_к1, а_к2,…,а_кn где при заданной функции упорядочения f справедливы отношения f(а_к1)£f(а_к2)£ …£f(а_кn). Обычно функция упорядочения f не вычисляется по какому-то специальному правилу, а является ключом элемента.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке; неустойчивым – в противном случае.

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

1) сортировка вставками;

2) сортировка выбором;

3) сортировка обменом.

Все сортировки представляют собой поиск со вложенными циклами. Сложность сортировок обменом и выбором: O(N²). Особенность же сортировки включением в том, что данная сортировка зависит от степени упорядочивания исходной таблицы.

Рассмотрим улучшенные методы сортировок:

1) Сортировка Шелла. – это улучшенный метод сортировки включениями. Был предложен Д.Л. Шеллом в 1959 г. Рассмотрим этот метод на примере.

Пример:

Первичный массив ключей	X1	X2	X3	X4	X5	X6	X7
Просмотр 1 Шаг 5 Проходов 5
Просмотр 2 Шаг 3 Проходов 3
Просмотр 3 Шаг 1 Проходов 1
Отсортированный массив ключей

При первом просмотре группируются и сортируются элементы, отстоящие друг от друга на 5 позиций: (Х₁,Х₆), (Х_2,Х₇), (Х₃), (Х₄), (Х₅); при втором проходе — элементы, отстоящие друг от друга на три позиции: (Х₁,Х_4,Х₇), (Х_2,Х₅), (Х_3,Х₆); при третьем — на 1 позицию.

Поскольку первый в сортировке Шелла используемый шаг является большим, отдельные подмассивы достаточно малы по отношению к исходным. Таким образом, сортировка включением над этими подмассивами работает достаточно быстро – О(N²) (эффективно при малом N). Сортировка каждого подмассива приводит к тому, что весь массив становиться ближе к отсортированному виду, что также делает эффективным использование сортировки включением. Так как массив становится более упорядоченным, то О(N) < порядок ФBC < О(N²).

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

В случае правильного выбора шагов порядок ФВС будет выглядеть как О(N^1.2). Д. Кнут предложил выбирать шаги из следующего ряда: 1, 4, 13, 40, 121, …, а вычислять их по следующей формуле: h_k–1 = 3* h_k +1; h_t = 1; t = [log ₃ N] – 1 (количество просмотров), где N – размерность исходного массива. Т.е. элементы должны быть взаимно простыми числами. Исходя из этого порядок сортировки может быть аппроксимирован величиной О(N(log ₂ N)).

2) Быстрая сортировка выбором. Улучшить сортировку выбором можно, если после каждого прохода получать больше информации, чем просто идентификация минимального элемента.

Пример:

k1	k2	k3	k4	k5	k6	k7	k8
10
10

10 – элемент MaxInt.

k1*(N-1) – количество просмотров; log ₂ N – высота бинарного дерева.

Мы проходим от корня к листу по тому пути, по которому шел минимальный элемент (шаг 2). Затем осуществляем модификацию бинарного дерева. Общее количество модификаций: k2*log ₂ N * (N-1).

Алгоритм быстрой сортировки выбором:

1. Сравниваем пары соседних ключей и запоминаем значение меньшего ключа из каждой пары.

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

3. Вносим значение корня, найденное в п.2, в массив упорядоченных ключей.

4. Проходим от корня к листу дерева, следуя по пути, отмеченному минимальным ключом, и заменяем значение в листе на наибольшее целое число.

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

6. Повторяем пп.3-6, пока минимальным элементом не будет MaxInt.

Анализ быстрой сортировки выбором.

k1*(N-1)+ k2*log ₂ N*(N-1) = О(N * log ₂ N) (ФВС = порядок)

2) Быстрая обменная сортировка (сортировка Хоара) – лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар окрестил его быстрой сортировкой. Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.

Алгоритм быстрой обменной сортировки:

1. Выбираем первый ключ в таблице в качестве разделителя.

2. Располагаем ключи меньшие разделителя до него, а большие – после.

3. Если число ключей до разделителя больше 1, то применяем алгоритм в целом.

4. Если число ключей после разделителя больше 1, то применяем алгоритм в целом. Конец алгоритма.

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

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

30
30	(10						60)
……………………………………………………………………….
(10			15)		(40		60)
……………………………………………………………………….

Анализ сортировки Хоара.

· Количество элементов N = 2^m, m = log ₂ N, где N – количество элементов.

· Будем считать, что разделитель попадает в середину массива.

Подсчитаем количество сравнений:

Если воспользоваться алгоритмом на упорядоченную таблицу, то порядок будет O(N²).

Для определения разделителя имеются разные алгоритмы.

Классификация задач по временной сложности.

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

По временной сложности все задачи классифицируются следующим образом:

1 класс. Задачи класса Р – это задачи, для которых известен алгоритм и временная сложность оценивается полиномиальной функцией f(N) = a _k*N + a _k-1*N ² +…+a ₀*N ^k+1. Алгоритмы таких задач называют также “хорошими” алгоритмами. Этих алгоритмов мало, они образуют небольшой по мощности класс. Легко реализуются. Функция временной сложности для таких алгоритмов имеет вид O(N^k).

2 класс. Задачи класса Е – это задачи, для которых алгоритм известен, но сложность таких алгоритмов O(f ^N), где f – константа. Задачи такого класса – это задачи построения всех подмножеств некоторого множества, задачи построения всех полных подграфов графа. При небольших N экспоненциальный алгоритм может работать быстрее полиномиального.

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

N
1000N^2	4 мкс	10 мкс	25 мкс	100 мкс	400 мкс	2.5 мс	10 мс	1 с
100N^3	1 мкс	3 мкс	18.5 мкс	100 мкс	800 мкс	13 мс	100 мс	100 с
2^N	4 мс	8 мс	30 мс	1 мкс	1 мс	10 сут.	Миллиарды лет
	16 мс	250 мс	30 с	Миллиарды лет

Дата добавления: 2014-01-07