Пусть имеется множество A=={б1,…, бp} выберем среди элементов б1,…, бp наибольший и обменяем его местами с первым. Выберем среди элементов б2,…, бp наименьший и обменяем его местами со вторым и т.д. На i-ом шаге выберем среди элементов бi,…, бp наименьший и обменяем его местами с i-ым, продолжать будем до тех пор, пока не достигнем последнего элемента.
Реализация алгоритма.
Составим процедуру сортировки линейного целочисленного массива с помощью прямого выбора.
Procedure ChooseSort( var a:TintVec; p:integer);
Var i, j, x, k:integer;
Begin
For i:=1 to p-1 do (1)
Begin
x:=a[i];
k:=i;
For j:=i+1 to p do
If a[j]<x then
Begin (2)
k:=j;
x:=a[j];
End;
a[k]:=a[i];
a[i]:=x; (3)
End;
End;
Описание программы.
Блок (10 реализует просмотр множеств элементов от i до p (последнего элемента). Блок (2) реализует выбор наименьшего элемента среди элементов с номерами от i до p. Блок (3) реализует обмен наименьшего элемента и i-ого.
Анализ алгоритма.
Оценим количество обменов элементов. Минимальное количество Mmin=3*(p-1), среднее число обменов Mср»p*(lnp+1), максимальное число обменов Mmax==(p*p)/4+3.
Описание алгоритма.
Будем рассматривать линейный массив как вектор столбец.
Сначала рассмотрим элементы от первого до последнего. Начиная с последнего элемента, будем рассматривать пары соседних элементов, если « верхний» элемент больше(тяжелее) «нижнего», то обменяем их местами. Указанный процесс обмена повторим для всех множеств от i до р.
Пример
11 11 11 11 1 1 1 1 1 1 1
3 3 3 1 11 11 11 3 3 3 3
5 5 1 3 3 3 3 11 11 4 4
4 1 5 5 5 5 4 4 4 11 5
1 4 4 4 4 4 5 5 5 5 11
При последовательных обменах более «легкие» элементы ( с меньшими значениями) как бы всплывают наверх, а более «тяжелые» оседают вниз. За такую особенность указанный алгоритм получил название пузырьковой сортировки.
Составим процедуру сортировки линейного целочисленного массива методом сортировки простым обменом.
Procedure Bubble Sort(p: integer; var a:TIntVec);
Var i,j,x: integer;
Begin
For i:=1 to p do
For j:=p downto I do
if a[j]<a[j-1] then
begin
x:=a[j-1];
a[j-1]:=a[j];
a[j]:=x;
end;
end.
Количество обменов:
Mmin=0
Mmax=3(n*n-n)/4
Mcp=3(n*n-n)/2
Общие замечания:
Рассмотрим линейный массив:
44, 55, 12, 42, 94, 18, 6, 67
Запишем его следующим образом: в первой строчке первый элемент, во второй строчке следующие два, а в третьей следующие 4 и т.д.
44
55 12
42 94 18 6
Дерево состоит из вершин, связанных отношениями, в нашем случае отношения обозначены прямой линией. Если из каждой вершины выходит не более двух линий такое дерево называется бинарным, если не более трех то тернарным.
Вершину из которой исходит хотя бы одна линия (ветвь) назовем отцом, вершины связанные с отцом ветвью, исходящей из него назовем сыновьями. Вершину у которой нет отца назовем корнем дерева или главным отцом.
В общем случае при представлении дерева в виде массива, к-ый элемент является отцом для 2*к и 2*к+1
к
2*к 2*к+1
Если массив имеет р элементов, то к лежит в интервале[1;[p/2]].
Описание алгоритма.
Алгоритм бинарной пирамидальной сортировки состоит из двух этапов:
Этап 1.
На этом этапе элементы массива переставляются таким образом, чтобы выполнились соотношения
a[k]≥a[2*k] (1)
a[k]≥a[2*k+1]
Другими словами строится пирамида (дерево) в которой значение вершины отца не меньше значения вершин сыновей.
в результате указанной перестановки корень дерева ( вершина пирамиды) будет содержать наибольшие значения среди элементов массива.
Этап 2.
Обменяем местами первый и последний элементы полученного массива размера р. Затем поставим первый элемент на соответствующее место в пирамиде образованной массивом из (р-1) элемента. Повторим указанную процедуру, пока в пирамиде не останется один элемент.
Рассмотрим этапы более подробно:
Этап 1.
Рассмотрим дерево, порожденное частью массива от элемента (L+1) до R предположим, что для него выполняется соотношение(1). Мы хотим в этом дереве разместить элемент с номером L a[L] так, чтобы условия (1) не нарушились для этого используем процедуру просеивания Shift(L,R).
Для элемента с номером L возможны следующие случаи:
1. не имеет потомков
2L>R
2. один потомок
2L=R
3. два потомка
2L<R
В случае (1) никаких действий не будет производиться.
В случае (2) обменяем местами элементы a[L] и a[R].
В случае (3) элемент a[L]имеет потомков a[2L] и a[2L+1]. К присвоим номер наибольшего из элементов a[2L] и a[2L+1], если a[L] < a[К], то обменяем их местами и применим процедуру Shift для установки элемента a[К] в дереве от (К-1) до R.
Пример.
Дан массив 44, 55, 12, 42, 94, 18, 6, 67.
Построим исходное дерево.
44
55 12
42 94 18 6
для него проведем указанную процедуру просеивания для всех L принадлежащих [[р/2];1].
Р=8
R=р=8
L=4
44
55 12
67 94 18 6
44
p=8
R=p=8 55 18
L=3
K=6 67 94 12 6
44
L=3
K=6 55 18
67 94 12 6
L=2 44
K=5
55 18
67 94 12 6
44
K=5
94 18
67 55 12 6
44
L=1
K=2 94 18
67 55 12 6
94
L=2
K=4 44 18
67 55 12 6
94
67 18
44 94 12 6
Этап 1 заключается в последовательном просеиваивании элемента массива с номером L в дереве от (L+1) до R. Для всех L от р/2 до 1.
Этап 2. Сначала рассмотрим весь массив от 1 до р. Обменяем местами первый и последний элемент с помощью процедуры Shift в дереве от 1 до (р+1) и продолжим, пока в дереве не останется только один элемент.
А лгоритм пирамидальной сортировки гарантирован в любом случае выполняет не более [c*p*ln p] обменов , где c- константа сравнимая с р.
Пример.
Дан исходный массив:
44, 55, 12, 42, 94, 18, 6 ,67 L=4
44, 55, 12, 67, 94, 18, 6, 42 L=3
44, 55, 18, 67, 94, 12, 6, 42 L=2
44, 94, 18, 67, 55, 12, 6, 42 L=1
94, 44, 18, 67, 55, 12, 6, 42
94, 67, 18, 44, 55, 12, 6, 42 L=1, R=8
42, 67, 18, 44, 55, 12, 6, 94
67, 42, 18, 44, 55, 12, 6, 94
67, 55, 18, 44, 42, 12, 6, 94 R=7
6, 55, 18, 44, 42, 12, 67, 94
55, 6, 18, 44, 42, 12, 67, 94
55, 44, 18, 6, 42, 12, 67, 94 R=6
12, 44, 18, 6, 42, 55, 67, 94
44, 12, 18, 6, 42, 55, 67, 94
44, 42, 18, 6, 12, 55, 67, 94 R=5
12, 42, 18, 6, 44, 55, 67, 94
42, 12, 18, 6, 44, 55, 67, 94 R=4
6, 12, 18, 42, 44, 55, 67, 94
18, 12, 6, 42, 44, 55, 67, 94 R=3
6, 12, 18, 42, 44, 55, 67, 94
12, 6, 18, 42, 44, 55, 67, 94 R=2
6, 12, 18, 42, 44, 55, 67, 94
§ 6.Алгоритм «быстрой сортировки.
Данный алгоритм был предложен Ч. Хоаром.
Описание алгоритма.
Рассмотрим произвольный массив
≤x x ≥x
выберем произвольный элемент массива х. Далее перестроим массив таким образом, чтобы в части от первого элемента до х располагались не превосходящие х, а в части от х до последнего элемента не меньшие х.
Для этого находим пары элементов не удовлетворяющих условию и меняем их местами. Далее такой алгоритм применим к левой и правой частям массива.
Пример:
11, 5, 13, 10, 8, 14, 6
6, 5, 13, 10, 8, 14, 11
6, 5, 8, 10, 13, 14, 11
6, 5, 8, 10 10, 13, 14, 11
5, 6, 8, 10 10, 11, 14, 13
5, 6 6, 8, 10 10,11 11, 14, 13
11, 13, 14
5,6,8,10,11,13,14
Алгоритм Хоара связан с выбором элемента х как границы между частями массива, чем «лучше» пограничный элемент х, тем «быстрее» происходит сортировка.
В массиве существует элемент называемый медианой, т.е. количество меньших его равно количеству больших его. Наиболее удобным будет выбирать медианы в качестве х, но поиск медианы сопряжен с существенными вычислительными затратами. В большинстве случаев в качестве х-пограничного элемента в части массива от L до R выбирают элемент [(R+L)/2].
Procedure QuickSoft( Var a: TIntVec; L,R: integer);
Var i,j,x,w: integer;
Begin
i:=L; (1)
j:=R;
x:=a[(L+R) div 2];
repeat
Whill a[i]<x do
i:=i+1; (2)
whill a[j]>x do (3)
j:=j-1;
if i<=j then
begin
w:=a[i];
a[i]:=a[j];
a[j]:=w; (4)
i:=i+1;
j:=j-1;
end;
until i>j;
if L<j then QuickSoft(a,L,j); (5)
if R>i then QuickSoft(a,I,r);
end;
описание процедуры:
Блок 1 выполняет начальную предустановку значений переменных.
В блоке 2 находим элемент больший зафиксированного.
В блоке 3 находим элемент меньше зафиксированного.
В блоке 4 производим обмен найденных элементов.
Повторяем блоки 2, 3, 4 до тех пор, пока каждый из индексов левой и правой части не выйдет за границы своей части.
В блоке 5 вызываем процедуру QuickSoft для левой и правой частей массива.
Быстрая сортировка является достаточно хорошим методом, если у нас есть массив размера р, то в среднем выполняется не более с*р*ln p обменов, но при неудачном выборе граничного элемента (когда он больше всех остальных элементов) требуется число обменов пропорциональное с*р*р.
Begin
a[k]:=a[i];
44
42 94 18 6
к
a[k]≥a[2*k] (1)
≤x x ≥x
Whill a[i]<x do
whill a[j]>x do (3)
if i<=j then
end;