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

Метод сортировки простым выбором основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Понятно, что поиск наименьшего ключа из n элементов требует n-1 сравнений, а поиск его среди n-1 элементов требует n-2 сравнений. Улучшение этой сортировки можно сделать только в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью n/2 сравнений можно определить наименьший ключ из каждой пары, при помощи следующих n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т. д. Наконец, при помощи всего n-1 сравнений мы можем построить дерево выбора и определить корень как наименьший ключ.

На втором шаге мы спускаемся по пути, указанному наименьшим ключом, и исключаем его, последовательно заменяя на «дыру». Затем заполняем «дыры».

Элемент, оказавшийся в корне дерева, вновь имеет наименьший ключ (среди оставшихся) и может быть исключен. После n таких шагов дерево становится пустым (т. е. состоит из «дыр») и процесс сортировки закончен. Отметим, что каждый из n шагов требует лишь сравнений. Поэтому вся сортировка требует лишь порядка элементарных операций, не считая n шагов, которые необходимы для построения дерева. Это значительное улучшение по сравнению с простым методом, требующим n² шагов, и даже по сравнению с сортировкой Шелла, которая требует n^1,2 шагов.

Избавиться от необходимости в дырах ( ), которые в конце заполняют все дерево и приводят к большому количеству ненужных сравнений и найти способ представить дерево из n элементов в n единицах памяти вместо 2n-1 единиц, как показано выше, можно с помощью метода, который Дж. Уильямс назвал пирамидальной сортировкой. Ясно, что этот метод дает существенное улучшение по сравнению с более привычными способами сортировки по дереву.

Достоинства: Самый быстрый из алгоритмов, не требующих дополнительной памяти; Имеет доказанную оценку худшего случая O(n log n).

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

Быстрая сортировка

Эта сортировка основана на принципе обмена. Усовершенствование сортировки, основанной на обмене, дает лучший метод сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель К. Хоор назвал его быстрой сортировкой.

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

Рассмотрим следующий алгоритм: выберем случайным образом какой-то элемент (x), просмотрим массив, двигаясь слева направо, пока не найдем элемент a[i] > x, а затем просмотрим его справа налево, пока не найдем элемент а[j] < x. Теперь поменяем местами эти два элемента и продолжим процесс «просмотра с обменом», пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую – с ключами, меньшими, чем x, и правую – с ключами, большими x.

Если, например, в качестве x выбрать средний ключ, равный 42, из массива ключей

44 55 12 42 94 06 18 67,

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

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

Тем не менее, остается проблема наихудшего случая. Здесь проявляется слабость быстрой сортировки (которая в таких случаях становится «медленной сортировкой»). Например, когда каждый раз в качестве x выбирается наибольшее значение в подмассиве. Тогда каждый шаг разбивает сегмент из n элементов на левую часть из n - 1 элементов и правую часть, состоящую из одного элемента. В результате вместо log(n) необходимо n разбиений и скорость работы в наихудшем случае оказывается порядка n².

Достоинства:
- Самый быстродействующий из всех существующих алгоритмов обменной сортировки — быстрее него только специализированные алгоритмы, использующие специфику сортируемых данных; ƒ

- Простая реализация; ƒ

- Хорошо сочетается с алгоритмами кэширования и подкачки памяти; ƒ

- Хорошо работает на «почти отсортированных» данных — если исходный массив уже близок к отсортированному, алгоритм не приводит к излишним перестановкам уже стоящих в правильном порядке элементов.

Недостатки:
- При классической реализации требует в худшем случае много дополнительной памяти. Правда, вероятность возникновения худшего случая ничтожна; ƒ

- Неустойчив — если требуется устойчивость, приходится расширять ключ

Рекурсивные структуры данных. Их реализация с помощью указателей. Линейные списки. Включение в список, удаление из списка, поиск в списке. Двунаправленные и циклические списки. Мультисписки. Топологическая сортировка.

Рекурсивные алгоритмы

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

В общем виде рекурсивную программу P можно выразить как некоторую композицию ρ из множества операторов S (не содержащих P) и самой P: P = ρ [S, P]. Если некоторая процедура P содержит явную ссылку на саму себя, то ее называют прямо рекурсивной, если же ссылается на другую процедуру Q, содержащую (прямую или косвенную) ссылку на P, то Р называют косвенно рекурсивной.

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

1) P = IF B THEN ρ [S, P];

2) P = ρ [S, IF B THEN P].

Рекурсивные алгоритмы особенно подходят для задач, где обрабатываемые данные определяются в терминах рекурсии. Однако это не означает, что такое рекурсивное определение данных гарантирует бесспорность употребления для решения задачи рекурсивного алгоритма. Рекурсивные схемы естественны в ситуациях, где вычисляемые значения определяются с помощью простых рекуррентных отношений. Существуют более сложные схемы рекурсий, которые необходимо переводить в итеративную форму. В качестве примера можно привести вычисление чисел Фибоначчи, определяемых рекурсивным соотношением fib_n+1=fib_n+fib_n-1 для n>0 и fib₁=1, fib₀=0. Прямое переписывание приводит к рекурсивной программе:

Function Fib(n:Integer):Integer;

Begin

If (n = 0) Then Fib := 0

Else

If (n = 1) Then Fib := 1

Else Fib := Fib(n - 1) + Fib(n - 2)

End;

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

i := 1; x := 1; y := 0;

While (i<n) Do

Begin

z := x; x : = x + y; y := z; i := i+1

End;

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

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

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