Анализ сортировки ШеллаАнализ этого алгоритма поставил несколько проблем. Не известно, какие расстояния дают наилучшие результаты. Д.Кнут в работе "Искусство программирования для ЭВМ" показывает, что имеет смысл использовать такую последовательность ( записана в обратном порядке): 1, 4, 13, 40, 121, ... или 1, 3, 7, 15, 31, ... Математический анализ показывает, что в последнем случае для сортировки n элементов методом Шелла затраты пропорциональны n1.2. Сортировка с помощью дереваМетод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n-1 элементов и т.д. Обнаружение наименьшего среди n элементов требует - это очевидно - n-1 сравнения, среди n-1 нужно n-2 сравнений и т.д. Сумма первых n-1 целых равна 1/2(n2-n). Как же в таком случае можно усовершенствовать упомянутый метод сортировки? Этого можно добиться, только оставляя после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Например, сделав n/2 сравнений, можно определить в каждой паре ключей меньший. С помощью n/4 сравнений - меньший из пары уже выбранных меньших и т.д. Проделав n-1 сравнений, мы можем построить дерево выбора и идентифицировать его корень как нужный нам наименьший ключ. Рассмотрим тот же массив: 44 55 12 42 94 18 06 67. Из двух соседних будем выбирать наименьший. 06
12 06
44 12 18 06 44 55 12 42 94 18 06 67 Повторяющиеся выборы среди двух ключей. Второй этап сортировки - спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путем замены либо на пустой элемент (дырку) в самом низу, либо на элемент из соседней ветви в промежуточных вершинах. 12 ? 44 12 18 ? 44 55 12 42 94 18 ? 67 Выбор наименьшего ключа. 12 12 18 44 12 18 67 44 55 12 42 94 18 ? 67 Заполнение дырок. Элемент, передвинувшийся в корень дерева, вновь будет наименьшим (теперь уже вторым) ключом, и его можно исключить. После n таких шагов дерево станет пустым (т.е. в нем останутся только дырки), и процесс сортировки заканчивается. Обратите внимание - на каждом из n шагов выбора требуется только n·logn элементарных операций плюс еще n шагов на построение дерева. Это весьма существенное улучшение. Естественно, сохранение дополнительной информации делает задачу более изощренной, поэтому в сортировке по дереву каждый отдельный шаг усложняется. Наша следующая задача - найти приемы эффективной организации этой информации. Это удалось добиться в методе Heapsort, изобретенном Д.Уилльямсом. Пирамида определяется как последовательность ключей hL, hL+1,...,hR, такая, что hi<=h2i и hi<=h2i+1 для i=L...R/2. h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 h11 h12 h13 h14 h15 Предположим, есть некоторая пирамида с заданными элементами hL+1,...,hR для некоторых значений L и R и нужно добавить новый элемент x, образуя расширенную пирамиду hL,...,hR. Возьмем, например, в качестве исходной пирамиду h1,...,h7 h1 42 06 55 94 18 12 и добавим к ней слева элемент h1=44. Новая пирамида получается так: сначала x ставится наверх древовидной структуры, а затем он постепенно опускается вниз каждый раз по направлению наименьшего из двух примыкающих к нему элементов, а сам этот элемент передвигается вверх. В приведенном примере значение 44 сначала меняется местами с 06, затем с 12 и в результате образуется дерево 06 42 12 55 94 18 44 Р.Флойдом был предложен способ построения пирамиды "на том же месте". Его процедура сдвига представлена в программе процедурой sift. Процесс формирования пирамиды из n элементов h1,...,hn на том же месте описывается так: L:=(n div 2) +1; while L>1 DO begin L:=L-1; sift(L,n); end; Для того чтобы получить не только частичную, но и полную упорядоченность среди элементов, нужно проделать n сдвигающих шагов, причем после каждого шага на вершину дерева выталкивается очередной (наименьший) элемент. type mass=array[1..100] of integer; var k,i,j,x: integer; a: mass; procedure sift ( var a: mass; l,r: integer); 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 x:=a[i]; a[i]:=a[j]; a[j]:=x; i:=j; j:=2*j; if (j<r) and (a[j]<a[j+1]) then j:=j+1; end; end; procedure Heapsort (var a: mass; n: integer); var l,r: integer; begin l:=(n div 2)+1; r:=n; while l>1 do begin l:=l-1; sift(a,l,r); end; while r>1 do begin x:=a[1]; a[1]:=a[r]; a[r]:=x; r:=r-1; sift(a,l,r); end; end; Begin randomize; readln(k); for i:=1 to k do begin a[i]:=random(100);write(a[i],' '); end; writeln; heapsort(a,k); writeln; for i:=1 to k do write(a[i],' '); writeln; End. |