Сортировка Хоара (QuickSort).

Метод быстрой сортировки был разработан Ч.Ф.Р.Хоаром и он же дал ему это название. В настоящее время этот метод сортировки считается наилучшим. Он основан на использовании обменного метода сортировки. Это тем более удивительно, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представляет собой простейшую версию обменной сортировки.

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

исходное состояние: f e d a c b;

первый проход:       d c a d e f;

второй проход:   a b c d e f.

Этот процесс продолжается для каждой части "abc" и "def". Фактически этот процесс имеет рекурсивную природу. И действтительно, наиболее "аккуратно" быстрая сортировка реализуется посредством рекурсивного алгоритма.

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

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

{ быстрая сортировка }

procedure qs(l, r: integer; var it: DataArray); {DataArray- это тип передаваемого массива, объявленный выше}

var

i, j: integer;

x, y: DataItem; {тип элемента массива}

begin

i:=l; j:=r;

x:=it[(l+r) div 2];

 repeat { цикл разделения массива на 2 части относительно среднего элемента}

………..

until i>j;

if l<j then qs(l, j, it);

if i<r then qs(i, r, it)

end;

Тело цикла разделения массива на 2 части относительно среднего элемента:

while it[i]<x do i := i+1;

while x<it[j] do j := j-1;

if i<=j then

begin

обмен местами элементов

   it[i] и it[j];

и изменение индексов i и j

end;

Сортировка пирамидальная.\

Произведем усовершенствование сортировки выбором: построим структуру данных, позволяющую выбирать максимальный элемент последовательности не за O(n), а за O(logn) времени. Тогда общее быстродействие сортировки будет n*O(logn) = O(n log n). Эта структура также должна позволять быстро вставлять новые элементы (чтобы быстро ее построить из исходного массива) и удалять максимальный элемент (он будет помещаться в уже отсортированную часть массива - его правый конец). Итак, назовем пирамидой(Heap) бинарное дерево высоты k, в котором все узлы имеют глубину k или k-1 - дерево сбалансированное. при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо, т.е форма пирамиды имеет приблизительно такой вид: выполняется "свойство пирамиды": каждый элемент меньше, либо равен родителю. Как хранить пирамиду? Поместим ее в массив. Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме: в a[0] хранится корень дерева левый и правый сыновья элемента a[i] хранятся, соответственнно, в a[2i+1] и a[2i+2] Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i] >= a[2i+1] и a[i] >= a[2i+2]. Плюсы такого хранения пирамиды очевидны: никаких дополнительных переменных, нужно лишь понимать схему. узлы хранятся от вершины и далее вниз, уровень за уровнем. узлы одного уровня хранятся в массиве слева направо. Запишем в виде массива пирамиду, изображенную выше.. Слева-направо, сверху-вниз: 94 67 18 44 55 12 06 42. На рисунке место элемента пирамиды в массиве обозначено цифрой справа-вверху от него.

Фаза 1 сортировки: построение пирамиды Hачать построение пирамиды можно с a[k]...a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i,j: i = 2i+1 ( или j = 2i+2 )... Просто потому, что такие i,j находятся за границей массива. Следует заметить, что неправильно говорить о том, что a[k]..a[n] является пирамидой как самостоятельный массив. Это, вообще говоря, не верно: его элементы могут быть любыми. Свойство пирамиды сохраняется лишь в рамках исходного, основного массива a[0]...a[n]. Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления - тот, который стоит перед уже готовой частью. Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]..a[n] на элемент a[i] влево: 1. Смотрим на сыновей слева и справа - в массиве это a[2i+1] и a[2i+2] и выбираем наибольшего из них. 2. Если этот элемент больше a[i] - меняем его с a[i] местами и идем к шагу 1, имея в виду новое положение a[i] в массиве. Иначе конец процедуры. Новый элемент "просеивается" сквозь пирамиду сдвигом по Флойду. Ниже дана иллюстрация процесса сдвига для пирамиды из 8-и элементов: 44 55 12 42 // 94 18 06 67    44 55 12 // 67 94 18 06 42    44 55 // 18 67 94 12 06 42      44 // 94 18 67 55 12 06 42    // 94 67 18 44 55 12 06 42 В геометрической интерпретации ключи из начального отрезка a[size/2]...a[n] является листьями в бинарном дереве. Один за другим остальные элементы продвигаются на свои места справа Итак, задача построения пирамиды из массива успешно решена.Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2: 1. Берем верхний элемент пирамиды a[0]...a[n] (первый в массиве) и меняем с последним местами. Теперь "забываем" об этом элементе и далее рассматриваем массив a[0]...a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент. 2. Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента. 3. Очевидно, в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность.   94 67 18 44 55 12 06 42    67 55 44 06 42 18 12 // 94   55 42 44 06 12 18 // 67 94   44 42 18 06 12 // 55 67 94   42 12 18 06 // 44 55 67 94   18 12 06 // 42 44 55 67 94   12 06 // 18 42 44 55 67 94   06 // 12 18 42 44 55 67 94

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

Применение

Алгоритм «сортировка деревом» активно применяется в ядре Linux.

Сортировка слиянием

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

Давайте посмотрим на такой массив:

Разделим его пополам:

И будем делить каждую часть пополам, пока не останутся части с одним элементом:

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

Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.

Для работы алгоритма мы должны реализовать следующие операции:

1. Операцию для рекурсивного разделения массива на группы

2. Слияние в правильном порядке

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

1. Открыть проект Delphi Structures.

2. На главной форме в главное меню добавить пункт «Лабораторная работа №3», при выборе которого должно появляться вертикальное подменю из двух пунктов:

1) SortBase

2) SortBest

Часть I (пункты 3÷6)

3. При выборе пункта 1) SortBase должно появляться окно модуля «Sortirovka1», для этого соответствующий модуль с формой необходимо добавить в проект.

4. Установить на форму модуля «Sortirovka1» компоненты, обеспечивающие ввод исходных данных, вывод результатов и управляющую кнопку, в соответствии с вариантом задания из таблицы 3.1.

5. В обработчике события onClick управляющей кнопки запрограммировать на языке Object Pascal алгоритм базовой сортировки в соответствии со своим вариантом задания. Отладить приложение и продемонстрировать работу преподавателю.

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

                                      Часть II (пункты 7÷10)

7. При выборе пункта SortBest должно появляться окно модуля «Sortirovka2», для этого в проект необходимо добавить соответствующий модуль с формой.

8. Установить на форму компоненты для ввода исходных данных, управляющую кнопку и для вывода результатов сортировки, в соответствии с вариантом задания из таблицы 3.2.

9. В обработчике события onClick запрограммировать и отладить алгоритм улучшенного метода сортировки в соответствии с вариантом. Продемонстрировать работу приложения преподавателю.

10. Составить отчет в соответствии с п.6, но, для улучшенных методов сортировки. Защитить всю работу преподавателю.

Таблица 3.1

Таблица 3.2

№ вар.	Текст задания
1.	var x: array [1..1000] of real; Применив алгоритм сортировки Шелла (сортировка с помощью включений с уменьшающимися расстояниями), отсортировать массив х в порядке неубывания. При выборе расстояний пользоваться следующими рекомендациями (Кнут Д. «Искусство программирования для ЭВМ» т.1): hk-1=2*hk-1 (…9,5,3,1), ht=1, t=[log2n] +1
2.	Используя сдвигающий алгоритм построения пирамиды Флойда, для заданного массива целочисленных ключей построить пирамиду, распечатать ключи получившегося бинарного дерева (например, в виде массива, для которого должно выполняться правило: для любого i: j=2*i или j=2*i+1, hi≤hj) и распечатать минимальный элемент массива.
3.	Пусть построена пирамида Флойда:                                                                     06 рис. 1   Ввести ключи этой пирамиды в ОП в виде массива, элементы которого подчиняются правилу задания бинарного дерева. Написать процедуру сдвига алгоритма Флойда и, используя ее, отсортировать ключи пирамиды в порядке убывания.
4.	Ввести ключи бинарного дерева (рис. 1) в ОП. Запрограммировать сдвигающий алгоритм Флойда для упорядочения заданного массива ключей в порядке возрастания (пирамидальная сортировка).
5.	Сформировать массив псевдослучайных целых чисел в диапазоне [-100…100]. Количество элементов задавать с клавиатуры. Используя рекурсивный алгоритм сортировки с помощью разделения (сортировка Хоара - QuickSort) упорядочить сформированный массив по неубыванию его элементов. Результат сортировки вывести в объект класса TMemo.
6.	Написать и отладить программу, которая использует итеративный алгоритм сортировки массива по убыванию с помощью разделения, в котором стек для запоминания требований (границы части массива, требующей дальнейшего разделения) необходимо организовать как массив записей с двумя целочисленными полями: var stack: array [1..30] of record Left, Right: integer; end;
7.	Запрограммировать и отладить алгоритм Хоара для нахождения медианы заданного массива целых чисел. Использовать рекурсивный алгоритм сортировки разделением.
8.	Сформировать массив целых псевдослучайных чисел в диапазоне [-20..20]. Отсортировать массив в порядке возрастания, используя алгоритм сортировки последовательностей прямым слиянием (алгоритм Боуза и Нельсона). Структурировать программу, организовав рекурсивную процедуру для слияния списков (частей массива) равного размера.

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

1. Определение сортировки, устойчивой сортировки.

2. Цель сортировки.

3. Сформулируйте полное условие окончания процесса сортировки прямым включением. Объясните применение приема «барьера», позволяющего сократить проверяемое условие.

4. Идея алгоритма двоичного включения, как модификация алгоритма прямого включения.

5. Приведите блок- схему алгоритма прямым выбором.

6. Что мы называем «пузырьком» в алгоритме метода сортировки прямым обменом?

7. В чем заключается модификация алгоритма пузырьковой сортировки, основанная на том, что в алгоритме просматривается ассиметрия: пузырьки на «тяжелом» и «легком» концах массива встают на свое место абсолютно по-разному.

8. Объясните на примере идею сортировки Шелла, как сортировки с помощью включений с уменьшающимися расстояниями.

9. Для последовательности ключей

     44 55 12 42 94 18 06 67  

постройте двоичное дерево выбора и идентифицируйте его корень.

10. Сформулируйте основное правило, с помощью которого можно прочитать пирамиду (двоичное дерево) в линейной последовательности ключей.

11. Объясните процедуру «сдвига элемента» в алгоритме Флойда.

12. Сформулируйте основную идею алгоритма быстрой сортировки Хоара.

13. Дайте определение i-той порядковой статистики, медианы.

14. Определение слияния последовательностей.

15. Основной недостаток методов сортировки слиянием.

Лабораторная работа №4