z [ ОJ :-п+X; m[0]:=0; z[l]:=1; m[l]:=n;

while k<>0 do begin Print (T,z,k) ; Sum:=m[k]*z[k]; if m[k]=l then begin k:=k-l;

Sura: -Sumi-m [ k ] * z [ k] end;

if z[k-l]=z[k]+l then begin k:=k-l; m[k] : =m[k] +1; end else begin z[k]:=z[k]+1; m[k]:=l;

end;

if Sum>z[k] then begin z[k+l]:=1; m[k+l] :=Sum-z[k];

k:=k+l end; end; end; {Divide)

Var {Main}

n : Integer; {Числе для разбиения) Hour,Minute,Second,SeclOO :Word; rHour,rMinute,rSecond,rSeclOO :Word; delta :Longlnt; begin

Assign(f, Divide.in) ; Reset ;f); {Файг открыт для чтения} ReadLn ( f, n ) ; {Чтение числа г:.} Close(f);

Assign ( f , Divide, out ) ;

открыт для GetTime (Hour,Minute, Second, SeclOO) ; Divide (n) ;

GetTime {rHour,rMinute, rSecond, rSeclOO)

delta:=rHour-Hour;

delta:=delta*60+rMinute-Minute;

delta:=delta*6 O + rSecond-Second;

delta:=delta*100+rSeclOO-SeclOO;

WriteLn(f, Бремя счета- , delta divlOO,* .,

delta mod 100, сек' ) ; Close (f) ; end.

4.8. Генерация случайных перестановок.

4.8. Генерация случайных перестановок

Пусть тс = (пьп2,..., п„) - произвольно выбранная перестановка целых чисел 1, п, например, я = (1,2,..., и) - тождественная. Случайную перестановку можно получить за линейное время О(п) из выбранной перестановки я = я->,..., ял). выполнив в ней п транспозиций (см. п.7.4).

Для промежуточных перестановок введем верхний индекс, значение которого будет соответствовать количеству выполненных транспозиций. Один из элементов в каждой транспозиции выбирается случайным образом. Индекс такого элемента устанавливается функцией rand(k,[), которая порождает независимые случайные целые числа на отрезке [к, I] с равномерным распределением.

Положим я(0) = (л<0) ,я(20),-, 40) равной исходной перестановке

я = (щ,пг.....лп). Каждая следующая перестановка п(к) = (л{[к) ,я{2к)

п\к') получается из предыдущей перестановки = (п\к^ ;, п[к'!}, ...,я 1))транспозициейэлементовя(ЛА 1) ия гдеА;= 1,2,...,

п. Между элементами перестановок п \ яя вьшолняются равенства л( = т^ !; ~...-к{к) где к=, 2,.,., п.

Покажем, что после выполнения всех указанных п транспозиций равновероятно получение любой из п! возможных перестано-вокст= (ai,o-2,..., ст ) исходных чисел я t, я2,..., я . Для этогодоста-точно проверить, что Рг(я(н) = а) = 1/л!.С этой целью введем события Аь А2,..., Ап.

Ак ИЦ -ок\п\*~ = a2&...<W/ ~/>

-~..л^

Вероятности данных событий, согласно схеме формирования перестановокп^°\ я(1\..., я , равны

Рг(Ак = 1/(л - к + 1), где к=\, 2..., п.

Условие л'.*-1 =ст,&л^-° -о2&...&д^:!) = ак. в событии к = 2,..., п, обеспечивает выбор элемента , из множества

(тгу* l),nKk~li\,..sit),k 1>}. которое совпадает с множеством {ак, aAti-- ац)- Индекс же rand(к, n) элемента является неза-

висимой случайной величиной с равномерным распределением на отрезке [к, n] целых чисел.

Теперь заметим, что

РГ(7Т(!) = СУ) РгЦ = ст1&Я2 ) =<У2&:.&Я$,Я> - <У„ ) =

= Рг(тг= & тгД2 - а 1 & .. .& тс, =cf ) =

PrJxPr.! )x...x?t{At) ={*{-*...х±=±.

Рассмотренный метод генерации случайной перестановки представлен в алгоритме 4.15.

Алгоритм 4.15, Генерация случайной перестановки

for k = 1 ton do щ = к; {Начальная перестановка}

fork= 1 ton - 1 do nk<r> к rand(kn); {Случайная перестановка)

или, если генерацию перестановки вести с конца,

for k = 1 ton do пк - к; {Начальная перестановка} fork=n to 2 do nk <-> nrand(lk); {Случайнаяперестановка).

- Глава 5 --

Сортировка и поиск

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

сравнений 0(nlog2n).

Задачу сортировки можно сформулировать так: дана последовательность из п элементов аь а2,..., а„, выбранных из множества, на котором задан линейный порядок, т.е. для любых а„ Oj выпол-няетсялибо а, < а;,либо щ < ар либо я, = а либо а, > ар либо а{ > ау Требуется найти перестановку = (п{,пг , пп этих элементов, которая отобразит данную последовательность в неубывающую последовательность а <яя <...<аж . Как правило, далее будем получать саму упорядоченную последовательность, а не упорядочивающую перестановку п.

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

менимы к данным, находящимся на внешних устройствах памяти, и имеют огромное коммерческое значение.

Внутренняя сортировка важна как для разработки алгоритмов, так и для коммерческих приложений. Сортируемые данные размещаются в оперативной памяти. Здесь рассматриваются именно методы внутренней сортировки данных. Известно много алгоритмов сортировки данных. Почему же так много методов сортировки? Ответ состоит в том, что каждый метод имеет свои преимущества и недостатки, поэтому он оказывается эффективнее других при некоторых структурах данных и аппаратной части.

Здесь же мы не пытаемся охватить даже те из них, которые считаются важными; скорее, мы ограничимся методами, оказавшимися полезными в разработке алгоритмов и в практической их реализации. Рассматриваемые здесь методы сортировки активно используются при разработке алгоритмов во многих разделах данного пособия. Полезно изучить характеристики каждого метода сортировки, чтобы можно было производить разумный выбор для конкретных приложений. К счастью, задача изучения этих алгоритмов не столь уж громоздка.

5.1. Сортировка вставками

Сортировка вставками элементов относится к наи-

более очевидным методам (алгоритм 5.1). Для компактности алгоритма вводится фиктивный элемент д0, значение которого устанавливается равным -оо. Сортировка проходит цикл для j = 2, 3,..., п; для каждогоу элемент щ вставляется в свое правильное место среди При вставке элемент разме-

щается в w и просматриваются имена д, 1; о^ 2>->ei они сравниваются с и сдвигаются вправо, если обнаруживается, что они болыие w. Имеется фиктивный элемент щ, значение которого -оо служит для остановки просмотра слева.

Алгоритм 5.1. Сортировка вставками

forj = 2 ton do

w=aj;

whdew<m doY**

[z=/ + l;

Сложность алгоритма определяется числом проверок условия <а,1 цикле. Сравнение <а, для конкретного = я, (/ > 2) выполняется 1 + яраз, где dj - число элементов, больших я,- и стоящих слева от него, т.е. dj - это число инверсий, у которых второй элемент о,. Числа dj составляют таблицу инверсий dxdv..dn, а так как 0 < iTi < л - 1, 0 < йг < п - 2,..., О < 4-1 < 1, dn = О, то в худшем

< JT (1+п -j)= - - -п- =д(п) сравнении. Сложность сортировки

вставками является квадратичной.

5.2. Пузырьковая сортировка

Рассматриваемый метод пузырьковой сортировки последовательности аь а2,..., ап представляет собой наиболее очевидный метод систематического обмена местами слева направо смежных элементов, не отвечающих выбранному порядку, до тех пор пока каждый элемент не оказывается на правильном месте. Эта техника получила название пузырьковой сортировки, так как большие элементы пузырьками всплывают вверх в конец списка. Реализация метода представлена алгоритмом 5.2. В алгоритме используется переменная Ь, значение которой при каждом проходе цикла устанавливается равным наибольшему индексу t, такому, что все элементы а1+1, а1+2,..., ап уже находятся на своих окончательных позициях. Ясно, что не имеет смысла продолжать просмотр для указанных элементов.

Сложность алгоритма определяется числом проверок условия

> в цикле и числом обменов которое равно числу

инверсий в исходной перестановке элементов аи а2,..., ап. Определим число сравнений. В худшем случае верхняя граница b - 1

случае сортировка элементов

а„ потребует £(1+) <

Алгоритм 5.2. Пузырьковая сортировка

Ь = л;

while b*Qdo\for j=\tob-\do ifa} > aj+l then I °J **° (b=t.

вложенного for на каждом шаге внешнего цикла while будет

уменьшаться на 1, тогда число сравнений равно У](£-1) = (я - 1) +

+(п -2) + ...+ 1 = - *--=0(п2). Сложность пузырьковой сортировки является квадратичной.

В алгоритме 5.3 представлена полная пузырьковая сортировка. Это наиболее популярный и упрощенный вариант алгоритма 5.2. Ясно, что основным достоинством алгоритма полной пузырьковой сортировки является легкость программирования. Сложность же алгоритма 5.3 остается постоянной, равной

= (п-1) + (п-2)+...+ 1 =-2- - = V(n Хине зависит отрас-

положения исходных данных.

Алгоритм 5.3. Полная пузырьковая сортировка

for i = 1 to n do begin

forj = 1 to n - i do begin

ifoj >aM thenaj<aM end; end.

5.3. Сортировка перечислением

Идея сортировки едовательности а >..... данных перечислением состоит в том, чтобы сравнить попарно все элементы ciy, сь,..., fl и подсчитать, сколько из них меньше каждого отдельного элемента (алгоритм 5.4). Для подсчета числа элементов, меньших в алгоритме используется вспомогательный вектор Cj, с2,..., сп. После завершения алгоритма значения су + \,j =\, 2,..., п определяют окончательное положение элементов в сортированной последовательности

Алгоритм 5.4. Сортировка перечислением

fori = ltondoci = Q { Сброситъсчетчики) for i = п to 1 by -1 do begin

forj = i - 1 to 1 by -1 do begin ifai>ajthenci=c,+ 1 elseC = cj+l end;

end;

for i = 1 ton do begin;

rc,+i =ai I ri-сортированные элементы) end.

Сложность алгоритма сортировки перечислением определяется парой вложенных циклов и составляет 0(п2). Величина сложности не зависит от расположения данных в исходной последовательности flj, Oi,..., ап.

Пусть перестановка л = {щ,к2>-, ял), гдетг,- = с,- + 1./= 1, 2,..., п. Алгоритм 5.4 сортировки перечислением определяет перестановку , которая соответствует расположению а , <а , <...<а ,

исходных данных

5.4. Сортировка всплытием Флойда

Все ранее упомянутые методы сортировки последовательности аь 02,..., ап требовали сравнений порядка 0(п ), и это никуда не годится . Рассмотрим один из наиболее элегантных и эффективных методов сортировки сложности предложенный Флойдом. До сих пор он остается самым оптимальным из существующих методов. В алгоритме активно используется упорядоченное двоичное дерево, пример которого представлен на рис. 5.1.

22 17 2 28

Рис. 5.1. Пример упорядоченного двоичного дерева

Значение в каждой его вершине не меньше, чем значение в его дочерних вершинах. Двоичное дерево называется частично упорядоченным, если свойство упорядоченности выполняется для каждой из его вершин, однако для корня это свойство нарушается. Пример частично упорядоченного дерева приведен на рис. 5,2.

39 96.

22 17 2 28

Рис. 5.2. Пример частично упорядоченного двоичного дерева

Интересно отметить, что в ранее рассмотренных методах сортировки сложности 0(п2) при выборе наибольшего (наименьшего) элемента, забывали информацию о других, забракованных элементах на эту роль, хотя эта проверка и выполнялась. Структура же дерева позволяет сохранить состояние процесса сортировки последовательности ап на каждом его шаге, с целью ис-

пользования этого состояния в дальнейших расчетах и уменьшения числа операций сравнений при поиске наибольшего (наименьшего) из оставшихся элементов.

Метод сортировки представлен в алгоритме 5.5, где

исходная последовательность данных представляется

в виде дерева на смежной памяти (одномерный массив а[1..п]). В таком дереве ребра присутствуют неявно и вычисляются с помощью арифметических операций над индексами элементов массива - смежной памяти. Пример двоичного дерева показан на рис. 5.3. Корень дерева - а[1], за каждой вершиной а[к] следуют вершины a[2k] и a[2k+l]. Использование смежной памяти для представления дерева имеет и другие преимущества, которые становятся очевидными после анализа алгоритма 5.5.

-а[1].

л[-Ц а[5] а|6 а[7]

Рис. 5.3. Пример двоичного дерева на смежной памяти

Основу алгоритма 5.5 составляет процедура SURFACE (a[i..k]) всплытия Флойда, которая за 0(log2 ) сравнений преобразует почти упорядоченное поддерево в упорядоченное. Поддерево представляется на одномерном массиве a[i..k], рис.5.4, где aij - корень поддерева, a[k] - максимальный элемент массива, который еще может принадлежать поддереву.

-a[ij

a[k]

Рис. 5.4. Двоичное поддерево на смежной памяти a[i..k]

Определим сложность процедуры SURFACE всплытия Флойда. Процедура заключается в том, что значение из корня (здесь может нарушаться условие упорядоченности) всплывает по направлению к листьям (последний уровень вершин в дереве) до тех пор, пока дерево не преобразуется в упорядоченное. Во время всплытия на каждом уровне выполняется конечное число С операций сравнения элементов. Если положить, что высота дерева (число уровней в дереве) равна Л, то сложность одного всплытия составите h = 0(h). Высота h регулярного двоичного дерева из и вершин легко находится из соотношения п < 2° + 21 +...+ 2Л 1, где 2~ - количество вершин на i-м уровне дерева, i = 1, 2,..., п. Отсюда высота дерева Л = [\og2(n + 1)1. Таким образом, сложность процедуры SURFACE всплытия Флойда составляет

Рассмотренная процедура SURFACE всплытия Флойда позволяет в почти упорядоченном дереве найти наибольший (наименьший) элемент за число сравнений 0(log2/t), преобразуя дерево к упорядоченному виду. В результате найденный элемент будет располагаться в вершине дерева. Для сортировки же множества элементов alla2,..., ап из них по алгоритму 5.5 сначала организуется почти упорядоченное двоичное дерево при помощи повторного применения алгоритма SURFACE всплытия Флойда сначала к самым мелким его поддеревьям от листьев и затем ко все более крупным. Листья тривиально упорядочены, поэтому можно начать с минимальных поддеревьев, содержащих несколько вершин, и укрупнять их, каждый раз полностью, применяя алгоритм всплытия до тех пор, пока таким образом не будет достигнут корень дерева. Заметим, что каждое из поддеревьев, к которым применяется алгоритм всплытия, удовлетворяет условию почти упорядоченности, поскольку упорядочивание проходит от листьев к корню. Именно таким способом в алгоритме 5.5 осуществляется формирование исходного почти упорядоченного дерева.

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

наибольшего (наименьшего) элемента множества при помощи

следующего применения процедуры SURFACE Флойда.

На рис. 5.5 показана полная последовательность перестановок и всплытий, которые происходят после формирования из исходно-

4-2697