Основы дискретной математики (стр. 4 из 23)
Если длина нашего массива равна n, нам нужно пройтись по n – 1 элементам. Каждый раз нам может понадобиться сдвинуть n – 1 других элементов. Вот почему этот метод требует довольно-таки много времени.
Сортировка вставками относится к числу методов сортировки по месту. Другими словами, ей не требуется вспомогательная память, мы сортируем элементы массива, используя только память, занимаемую самим массивом. Кроме того, она является устойчивой – если среди сортируемых ключей имеются одинаковые, после сортировки они остаются в исходном порядке.
Сортировка с помощью включения
Кто играл в карты, процедуру сортировки включениями осуществлял многократно. Как правило, после раздачи карт игрок, держа карты веером в руке, переставляет карты с места на место, стремясь их расположить по мастям и рангам, например, сначала все тузы, затем короли, дамы и т. д. Элементы (карты) мысленно делятся на уже «готовую последовательность» и неправильно расположенную последовательность. Теперь на каждом шаге, начиная с i = 2, из неправильно расположенной последовательности извлекается очередной элемент и перекладывается в готовую последовательность на нужное место.
for i:=2 to N do
begin
x:=a[i];
<включение х на соответствующее место готовой последовательности a[1],…, a[i]>
End
Поиск подходящего места можно осуществить одним из методов поиска в массиве, описанным выше. Затем х либо вставляется на свободное место, либо сдвигает вправо на один индекс всю левую сторону. Схематично представим алгоритм для конкретного примера:
Исходные элементы 23 34 12 13 9
i=2 23 34 12 13 9
i=3 12 23 34 13 9
i=4 12 13 23 34 9
i=5 9 12 13 23 34
В алгоритме поиск подходящего места осуществляется как бы просеиванием x: при движении по последовательности и сравнении с очередным a[j]. Затем х либо вставляется на свободное место, либо а[j] сдвигается вправо и процесс как бы «уходит» влево.
Сортировка с помощью прямого включения
Элементы массива, начиная со второго, последовательно берутся по одному и включаются на нужное место в уже упорядоченную часть массива, расположенную слева от текущего элемента а[i]. В отличие от стандартной ситуации включения элемента в заданную позицию массива, позиция включаемого элемента при этом неизвестна. Определим её, сравнивая в цикле поочерёдно a[i] с a [i‑1], а [i‑2],… до тех пор, пока не будет найден первый из элементов меньший или равный а[i], либо не будет достигнут левый конец массива. Поскольку операции сравнения и перемещения чередуются друг с другом, то этот способ часто называют просеиванием или погружением. Очевидно, что программа, реализующая описанный алгоритм, должна содержать цикл в цикле.
program sortirovka_l;
(*сортировка включением по линейному поиску*)
const N=5;
type item= integer;
var a: array [0..n] of item; i, j: integer; x: item;
begin (*заданиеискомогомассива*)
for i:=1 to N do begin write ('введитеэлементa [', i, ']=');
readln (a[i])
end;
for i:=1 to N do begin write (a[i], ' ');
end;
writeln;
(*алгоритм сортировки включением*)
for i:=2 to n do
begin
x:=a[i]; j:=i; a[0]:=x; (*барьер*)
while x<a [j-l] do
begin
a[j]:=a [j‑1]; j:=j‑1;
end;
a[j]:=x;
{for k:=1to n do write (a[k], ' ') end; writeln;} end;
(*вывод отсортированного массива*)
for i:=1 to N do
begin
write (a[i], ' '); end;
readln; end.
В рассмотренном примере программы для анализа процедуры пошаговой сортировки можно рекомендовать использовать трассировку каждого прохода по массиву с целью визуализации его текущего состояния. В тексте программы в блоке непосредственного алгоритма сортировки в фигурных скобках находится строка, которая при удалении скобок выполнит требуемое (параметр k необходимо описать в разделе переменных – var k:integer).
Вернемся к анализу метода прямого включения. Поскольку готовая последовательность уже упорядочена, то алгоритм улучшается при использовании алгоритма поиска делением пополам. Такой способ сортировки называют методом двоичного включения.
program sortirovka_2;
(*сортировка двоичным включением*)
const N=5;
type item= integer;
var a: array [0..n] of item; i, j, m, L, R: integer; x: item;
begin (*заданиеэлементовмассива*)
for i: – l to N do begin write ('введитеэлементa [', i, ']= ');
readln (a[i]);
end;
for i:=1 to N do begin write (a[i], ' ');
end;
writeln;
(*алгоритм сортировки двоичным включением*)
for i:=2 to n do
begin
x:=a[i]; L:=l; R:^i;
while L<R do
begin
m:=(L+R) div 2; if a [m] <=x then L:=m+1 else R:=m;
end;
for j:=i downto R+l do a[j]:=a [j‑1];
a[R]:=x; end;
(* вывод отсортированного массива*)
for i: – l to N do
begin write (a[i], ' ');
end;
readln;
end.
Сортировка Шелла
Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(n1.25), для худшего случая оценкой является O(n1.5). Дальнейшие ссылки см. в книге Кнута [4].
На рисунке 1.8 приведен пример сортировки вставками. Мы сначала вынимали 1, затем сдвигали 3 и 5 на одну позицию вниз, после чего вставляли 1. Таким образом, нам требовались два сдвига. В следующий раз нам требовалось два сдвига, чтобы вставить на нужное место 2. На весь процесс нам требовалось 2+2+1=5 сдвигов.
На рисунке 1.9 иллюстрируется сортировка Шелла. Мы начинаем, производя сортировку вставками с шагом 2. Сначала мы рассматриваем числа 3 и 1: извлекаем 2, сдвигаем 3 на 1 позицию с шагом 2, вставляем 2. Затем повторяем то же для чисел 5 и 2: извлекаем 2, сдвигаем вниз 5, вставляем 2 и т. д. Закончив сортировку с шагом 2, производим ее с шагом 1, т. е. выполняем обычную сортировку вставками. Всего при этом нам понадобится 1 + 1+ 1 = 3 сдвига. Таким образом, использовав вначале шаг, больший 1, мы добились меньшего числа сдвигов.
Рисунок 1.9 – Сортировка Шелла
Можно использовать самые разные схемы выбора шагов. Как правило, сначала мы сортируем массив с большим шагом, затем уменьшаем шаг и повторяем сортировку. В самом конце сортируем с шагом 1. Хотя этот метод легко объяснить, его формальный анализ довольно труден. В частности, теоретикам не удалось найти оптимальную схему выбора шагов. Кнут провел множество экспериментов и следующую формулу выбора шагов (h) для массива длины N.
Вот несколько первых значений h:
.Чтобы отсортировать массив длиной 100, прежде всего, найдем номер s, для которого hs³ 100. Согласно приведенным цифрам, s = 5. Нужное нам значение находится двумя строчками выше. Таким образом, последовательность шагов при сортировке будет такой: 13–4–1. Ну, конечно, нам не нужно хранить эту последовательность: очередное значение h находится из предыдущего.
Сортировка с помощью дерева
Улучшенный метод сортировки выбором с помощью дерева. Метод сортировки прямым выбором основан на поисках наименьшего элемента среди неготовой последовательности. Усилить метод можно запоминанием информации при сравнении пар элементов. Этого добиваются определением в каждой паре меньшего элемента за n/2 сравнений. Далее n/4 сравнений позволит выбрать меньший из пары уже выбранных меньших и т. д. Получается двоичное дерево сравнений после n‑1 сравнений, у которого в корневой вершине находится наименьший элемент, а любая вершина содержит меньший элемент из двух приходящих к ней вершин. Одним из алгоритмов, использующих структуру дерева, является сортировка с помощью пирамиды (Дж. Вильямс) [3]. Пирамида определяется как последовательность ключей hL…hR, такая, что
hi<=h2iиhi<=h2i+l, дляi=L,…, R/2.
Другими словами, пирамиду можно определить как двоичное дерево заданной высоты h, обладающее тремя свойствами:
• каждая конечная вершина имеет высоту h или h‑1;
• каждая конечная вершина высоты h находится слева от любой конечной вершины высоты h‑1;
• значение любой вершины больше значения любой следующей за ней вершины.
Рассмотрим пример пирамиды, составленной по массиву 27 9 14 8 5 11 7 2 3.
У пирамиды n=9 вершин, их значения можно разместить в массиве а, но таким образом, что следующие за вершиной из a[i] помещаются в a[2i] и a [2i+l]. Заметим, что а[6]=11, а[7]=7, а они следуют за элементом а[3]=14 (рисунок 1.10).
Рисунок 1.10 – Пирамида
Очевидно, что если 2i > n, тогда за вершиной a[i] не следуют другие вершины, и она является конечной вершиной пирамиды.
Процесс построения пирамиды для заданного массива можно разбить на четыре этапа:
1) меняя местами а[1] и а[n], получаем 3 9 14 8 5 11 7 2 27;
2) уменьшаем n на 1, т. е. n=n‑1, что эквивалентно удалению вершины 27 из дерева;
3) преобразуем дерево в другую пирамиду перестановкой
нового корня с большей из двух новых, непосредственно следующих за ним вершин, до тех пор, пока он не станет больше, чем обе вершины, непосредственно за ним следующие;
4) повторяем шаги 1, 2, 3 до тех пор, пока не получим n=1.
Для алгоритма сортировки нужна процедура преобразования произвольного массива в пирамиду (шаг 3). В ней необходимо предусмотреть последовательный просмотр массива справа налево с проверкой одновременно двух условий: больше ли а[n], чем a[2i] и a [2i+l].
Полный текст программы приведен ниже.
program sortirovka_5;
(*улучшенная сортировка выбором – сортировка с помощью дерева*)
const N=8;
type item= integer;
var a: array [1..n] of item; k, L, R: integer; x: item;
procedure sift (L, R:integer);
var i, j: integer; x, y: item;
begin i:=L; j:=2*L; x:=a[L]; if (j<R) and (a[j]<a [j+1]) then j:=j+1;
while (j<=R) and (x<a[j]) do begin y:=a[i]; a[i]:=a[j];
a[j]:=y; a[i]:=a[j]; i:=j; j:=2*j;
if (j<R) and (a[j]<a [j+1]) then j:=j+1;
end;
end;
begin
(*задание искомого массива*)