Сортировка с помощью двоичного дерева (пирамидальная)

АЛГОРИТМ 1. Построение сортирующего дерева

Вход: массив А[1..n].

Выход: элементы А организованы в виде сортирующего дерева,

т.е. A[i] >= max(A[2i],A[2i + 1]), 2i,2i+1 <= n.

procedure ПЕРЕСЫПКА(i,j):

1. IF (i - не лист) и (у i есть сын, содержащий

элемент , превосходящий элемент в i)

THEN

BEGIN

2. k := сын i, содержащий наибольший элемент;

3. переставить А[i] и A[k];

4. ПЕРЕСЫПКА(k,j)

END

procedure ПОСОРТДЕР:

FOR i = n STEP -1 UNTIL 1

5. DO ПЕРEСЫПКА(i,n)

АЛГОРИТМ 2. Сортировка деревом

Вход: массив A[1..n].

Выход: элементы А, расположенные в неубывающем порядке

BEGIN

ПОСОРТДЕР;

FOR i = n STEP -1 UNTIL 2

DO

BEGIN

1. переставить A[1] и A[i];

2. ПЕРЕСЫПКА(1,i-1)

END

END

БЫСТРАЯ СОРТИРОВКА (Хоар,1962)

АЛГОРИТМ 3.

Вход и выход как и в алгоритме 2.

BEGIN

БЫСТРСОРТ(1,n)

END

procedure БЫСТРСОРТ(i,j):

1. IF i < j

THEN

2. BEGIN выбрать произвольное k : i <= k <= j;

3. пусть A1 - подмассив элементов А[m] < A[k],

A2 - подмассив элементов А[m] = A[k],

A3 - подмассив элементов А[m] > A[k];

переставить элементы так, чтобы

А1 = А[i..j1], A2 = A[j1+1..j2],A3 = A[j2+1..j3];

4. БЫСТРСОРТ(i,j1);

5. БЫСТРСОРТ(j2+1,j3)

END

АЛГОРИТМ 4. ЛЕКСИКОГРАФИЧЕСКАЯ СОРТИРОВКА

------------

Вход: последовательность А1,А2,...,Аn, где

Аi = (ai1,...,aik), 1<= aij <= m.

Выход: перестановка входной последовательности в

лексикографическом порядке.

procedure ЛЕКС:

1. FOR i = 1,...,n

DO ДОБАВ(Q,Ai) END_DO;

2. FOR j=k STEP -1 UNTIL 1

DO

BEGIN

3. FOR t=1,2,...m

DO Qt := НОВ_ОЧЕРЕДЬ END_DO;

4. WHILE не ПУСТ(Q)

DO BEGIN

A := НАЧ(Q);

5. CASE A[j]

A[j]=1 : ДОБАВ(Q1,A);

....

A[j]=m : ДОБАВ(Qm,A)

END_CASE;

УДАЛ(Q)

END;

6. Q := Q1*Q2* ...*Qm

END.

Задача о k-ом наименьшем (наибольшем) элементе

АЛГОРИТМ 1. Нахождение k-го наименьшего элемента за линейное время

Вход: Последовательность А из n элементов: А = а1,...,аn,

и чичсло k, 0 < k < n+1.

Выход: k-ый наименьший элемент последовательности А.

procedure МИНК(k,A):

1. IF |A| < 50 /* n < 50 */

THEN BEGIN

2. отсортировать А;

3. выдать k-ый наименьший элемент А

END

ELSE

BEGIN

4. разбить А на подпоследовательности из 5 элементов:

А1,...,Аr , r = int(|A|/5);

5. останется < 5 элементов А;

6. FOR i=1,...,r

DO отсортировать Ai;

7. образовать последовательность М медиан этих

пятиэлементных множеств;

s :=int( |M|/2 );

8. m := МИНК(s,M); /* s - медиана М */

9. образовать последовательности АМ,АР и АБ элементов

А, которые соответственно меньше, равны и больше m;

IF |AM| >= k

10. THEN выдать МИНК(k,AM)

ELSE

IF (|AM| + |AP| >= k)

11. THEN выдать m

12. ELSE выдать МИНК(k - |AM|-|AP|,АБ)

END

АЛГОРИТМ 2. Нахождение k-го наименьшего элемента за линейное время в среднем.

Вход и выход как и в алгоритме 1.

procedure МИНСК(k,A):

1. IF |A| = 1

THEN выдать <единственный эл-т А>

ELSE BEGIN

2. случайно выбрать элемент a из А;

3. образовать последовательности АМ,АР и АБ элементов

из А, меньших, равных и больших а соответственно;

IF |AM| >= k

4. THEN выдать МИНСК(k,АМ)

ELSE

IF (|АМ|+|АР| >= k)

5. THEN выдать а

6. ELSE выдать МИНСК(k-|AM| ,|АР|,АБ)

END

=================================================

Задача 1. Упорядочить последовательность 3,1,2,4,1,3,8,2,1,6, применяя алгоритмы а) пузырьковой сортировки, б) сортировки слиянием, в) сортировки деревом, г) быстрой сортировки. Сколько сравнений производится в каждом случае?

Задача 2. Доказать, что время выполнения процедуры ПЕРЕСЫПКА для вершины высоты k есть O(k).

Задача 3. Написать на Паскале алгоритм, реализующий шаг 3 в процедуре БЫСТРСОРТ (т.е. осуществляющий разбиение и перестановку подмассивов А1,А2,А3) без использования дополнительного массива ("на месте").

Задача 4. Показать, что время работы БЫСТРСОРТ в худшем случае квадратично, т.е. O(n^2 ).

Задача 5. Используя алгоритм ЛЕКС упорядочить последовательность: ВОЛ, ЛОВ, ОВО, ВЛО, АЛО, ВАЛ, ЛАВ, ОВА.

Задача 6. Разработать алгоритм лексикографической сортировки цепочек разной длины.

(Указание: для каждого l <= (max длинa цепочек) создать упорядоченный список НЕПУСТ(l) символов, появляющихся на l-ом месте в цепочках; для каждого l создать список ДЛИНА(l) цепочек длины l; использовать эти структуры в алгоритме, аналогичном алгоритму ЛЕКС ).

Задача 7. Можно ли в алгоритме МИНК вместо разбиения А на подпоследовательности из 5 элементов разбивать А на подпоследовательности из 3,7,9 элементов? Какова сложность получающихся алгоритмов?

Задача 8. Какова сложность алгоритма МИНСК в худшем случае?