Begin quciksort();

Оценка эффективности быстрой сортировки

Опорный элемент делит последовательность в идеале почти пополам. Каждый из образовавшихся подпоследовательностей данного уровня иерархии рекурсивного вызова применяется тот же самый алгоритм так, в сумме по последовательностям quicksort обеспечивает встречное движение, а точнее всех переменных. Если последовательность упорядочена в обратном порядке, то опорный элемент, занимается крайнее левое или правое положение разбивает, обеспечивая максимальное количество число уровней глубины рекурсии n - 1, на каждом уровне просматривая N элементов. Таким образом, худшая оценка достигается в случае упорядоченности в подпоследовательности данных. Все алгоритмы по улучшению данных алгоритма Хоару сводится к выбору специальным образом опорного элемента так, чтобы разбиение по возможности происходило на середине отрезка.

Популярен алгоритм, в котором индекс опорного элемента получил название pivot.

Pivot:=(right-left) / 2 + left;

Все сравнения вида while k[i] > k[[j]  k[pivot]>k[i]

 k[pivot] < k[j];

Пирамидальная сортировка. Выбор из дерева

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

(олимпийская система, попарно)

1. 4 5 20 7 6 7 14 40

20

40 20 7 14 14

7

40 14 7

40

Такая организация в виде дерева обеспечивает минимальное сравнение ключей. В корне располагается наибольший или наименьший элемент, который затем извлекается из множества. На его место претендует наибольший (наименьший) из заместителей. Замещение вакантного места происходит до листа (дерева). А лист заменяется на – ∞, т.е. наименьшее число.

В 1968 году был предложен алгоритм, в котором отсутствовал элемент – ∞, а элементы располагались внутри самой последовательности. Такой алгоритм получил название пирамидально сортировки. Пирамидой называется последовательность Ключей к1 к2 кn, в которой выполняется K_{jdiv 2} >= K_j ; ,1 <= j div 2 <= N , причем ключи занумерованы в следующем порядке

1 K1

K 2 2 3 K3

2 j 4 2j+1 5 2j 6 7 2j+1

8 9 10 11 12 13 14 15

, то у узла K[j] сыновья будут с индексами 2j и 2j+1. Таким образом, в соответствии с формулой 1 пирамиды любой отец в пирамиде не превышает наименьшего из сыновей из своих сыновей, тогда корнем будет наименьший во всей последовательности. Алгоритм пирамидальной сортировки состоит из двух этапов:

1. Располагает произвольную последовательность в виде пирамиды

2. Последовательно исключаем вершину пирамиды и восстанавливаем условие j1 внутри последовательности.

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

15 7 5 14 40 6 7 20 -2

II -2 4 5 14 7 6 7 15

40 4 5 20 7 6 7 14

1 2 3 4 5 6 7 8

40

1. 5

10 -2 6 7

14 15 7

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

1

Z log ₂(n-i)

I N div 2

Log2(N(N-1))

0(f параметр) = const n log₂N

Сортировка подсчетом

Сортировка называется сравнение и подсчет.

40 4 5 20 7 14 15 -2 k

0 0 0 0 0 0 0 0 count

0 1 1 1 1 1 1 1

0 0 0 0 0 0 1

0 0 0 0 1

0 8 7 1 5 6 4 3 2

20

Count[i] – количество элементов ki.

Расстановка элементов в соответствии Result[Count [i] + 1]:=k[i]

Распределяющий подсчет

В этом алгоритме ключами могут быть целые числа или приводимые к целым в диапазоне от a до c.

Ki Э [a…c]

a ≤ Ki ≤ C

a = min{Ki} – O(n)

c = max{Ki} – O(n)

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

a = min{k}= 2

c = max{k} = 5

count [a…c]

4 2 4 5 4 2

0 0 0 0 count

2 3 4 5

2 0 3 1 count[k[i]++]

2 3 4 5

I этап инициализация массива count 0 0 0 0

II этап подсчет одинаковых ключей Count[i]++

1. 0 3 1

III этап – заметим, что значением самой правой ячейки count показывает, сколько ячеек необходимо зарезервивать в результирующем массиве под хранение значения K[i] . В данном случае одна ячейка отводится под хранение 5, три ячейки под значения 4, 0 ячеек – под тройку и две ячейки под значение двойки. При помощи цикла расположим элементы по зарезерванным позициям. Заметим, что тройки могли бы начать располагаться после всех двоек, т.е. после количества, указанной в count.. Четверки располагаются по двойки и тройки, т.е. с позиции count[2]+count[3], а прибавляя count [4] мы получаем самую правую позицию, которую может занять k[i] ключ.

IV этап – расположение элементов.

|c - a| - должно быть небольшое

2*O(N) + O(c-a) + O(N) + O(c-a-1) + O(N)= const O(N) + const O(c-a)

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

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

Естественное двухпутевое слияние – ЕДС

В обоих алгоритмах ЭДС и ФДС используется память объемом 2N. Попеременно одна область служит источником, а другая – получателем предупорядоченных последовательностей. В источнике одна предупорядоченная расположена слева направо, а другая справа налево (в конце). В каждый момент времени сравнивается очередные элементы подпоследовательностей (если они еще не пустые), и в результат записывается наименьший (наибольший из этой пары).

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

_ ______ _____________

3 4 2 5 3 10 15 10 8 11 5 2

2 3 4 5 11 3 10 15 10 8 5 2

2 2 3 4 5 5 8 10 11 15 10 3

2 2 3 3 4 5 5 8 10 10 11 15

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

Фиксированное двухпутевое слияние

3 4 2 5 3 10 15 10 8 11 5 2

2 3 2 11 3 10 15 10 8 5 5 4

2 3 4 5 3 10 10 15 11 8 5 2

2 2 3 3 4 5 5 8 10 10 11 15

Сравнивая, эффективности ЕДФ и ФДС заметим, что ФДС – предельный, наихудший случай ЕДС, поэтому при подсчете числа этапов слияния детерминированный количеством подпоследовательностью ФДС, i-том этапе ФДС количество элементов в слияемых последовательностях не превосходит 2ⁱ. Таким образом, количество этапов (наибольшее из возможных i), когда при объединение этих двух последовательностей. 2^(i - 1)+2^(i - 1) ≥ N

Таким образом, максимальное количество этапов фиксированное и равно log₂N, а на каждом этапе в сравнении участвуют все N ключей. (O)N=log₂N*const*N

Пример выполнения расчетов по практическому занятию

Задание: Написать программу реализации алгоритма пузырьковой сортировки для АТД «Очередь» (очередь с одной головой).

Решение:

type ochered=^Rec;

Rec=record

info: integer;

next: ochered;

end;

var

head, head1: ochered;

n, i, j, z, k, y, x, x1: integer;

nop:real;

procedure push(var head:ochered; x:integer); // 6

var a: ochered;

begin

new(a); //+1

a^.info:=x; //+2

a^.next:=head; //+2

head:=a; //+1

end;

procedure pop(var head:ochered; var x:integer); //8+

var a, p: ochered;

begin

a:=head; p:=head; //+2

while a^.next<>nil do begin //+2

p:=a; a:=a^.next; //+3

end;

x:=a^.info; p^.next:=nil; //+4

dispose(a); //+1