Алгоритмы и структуры данных

В худшем случае этот алгоритм дает временную сложность T_max(n), пропорциональную O(n²) (для случая, когда все выборки «среднего»

 

элемента оказались неудачны), но как показывают теоретические исследования, вероятность такого случая очень мала. В среднем же и в лучшем случае получим временную сложность T(n), пропорциональную O(nlog n).

2.5.2.8. Сортировка слиянием

Этот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов.

Пусть k - положительное целое число. Разобьем массив A[1]...A[n] на участки длины k. (Первый - A[1]...A[k], затем A[k+1]...A[2k] и т. д.) Последний участок будет неполным, если n не делится нацело на k. Назовем массив k-упорядоченным, если каждый из этих участков длины k упорядочен.

Ясно, что любой массив 1-упорядочен, так как его участки длиной 1 можно считать упорядоченными. Если массив k-упорядочен и n < k, то он упорядочен.

Рассмотрим процедуру преобразования k-упорядоченного массива в 2k-упорядоченный. Сгруппируем все участки длины k в пары участков. Теперь пару упорядоченных участков сольем в один упорядоченный участок. Проделав это со всеми парами, получим 2k-упорядоченный массив (рис. 47).

Слияние требует вспомогательного массива B для записи результатов слияния. При слиянии сравниваем наименьшие элементы участков рассматриваемой пары, и меньший из них заносим в массив B. Повторяем описанные действия до тех пор, пока не исчерпается один из участков. После чего заносим в массив B все оставшиеся элементы другого участка. Затем переходим к следующей паре участков:

procedure MergeSort(n:  integer;

var A: array[1..n] of integer); {Процедура сортировки слиянием} var

i, j, k, t, s, Start1, Fin1, Fin2: integer; B: array[1..n] of integer; begin

k := 1;     {Начальное значение длины участков} 
while k < n do begin   {пока участок не весь массив} 
t := 0; {начало 1-й пары участков}

while t+k < n do begin   {пока не все участки просмотрели} {Определяем границы рассматриваемых участков} Start1 := t+1;   Fin1 := t+k;    {Начало и конец 1-го участка} if t+2*k > n then Fin2 := n

else Fin2 := t+2*k; {Конец 2-го участка} 
i := Start1;       {Начальное значение индекса в 1-м участке} 
j  := Fin1 + 1;    {Начальное значение индекса в 2-м участке} 
s := 1; {Начальное значение индекса в массиве B}

{Заполняем B элементами из двух участков} while (i <= Fin1) and (j <= Fin2) do begin

{Сравниваем попарно элементы из двух участков} if A[i] < A[j] then begin {Вставляем элемент из 1-го участка}

B[s] := A[i]; i := i + 1;

end else begin

{Вставляем элемент из 2-го участка}

B[s] := A[j];

j := j + 1; end;

s := s + 1;

end;

{Добавляем в массив B оставшиеся элементы из 1-го участка}

while (i <= Fin1) do begin

B[s] := A[i];

i := i + 1; s := s + 1; end;

{Добавляем в массив B оставшиеся элементы из 2-го участка} while (j <= Fin2) do begin B[s]   := A[j];

j := j + 1; s := s + 1;

end;

t := Fin2;       {Переходим к следующей паре участков} end;

k := k * 2;    {Удваиваем значение длины участков} {Сохраняем полученный промежуточный результат}

for s := 1 to t do A[s] := B[s];

end; end;

Сразу же бросается в глаза недостаток алгоритма - он требует дополнительную память размером порядка n (для хранения вспомогательного массива). Кроме того, он не гарантирует сохранение порядка элементов с одинаковыми значениями. Но его временная сложность всегда пропорциональна O(nlog n) (так как преобразование k-упорядоченного массива в 2k-упорядоченный требует порядка n действий и внешний цикл по k совершает порядка log n итераций).

2.5.2.9. Сортировка распределением

Сортировка распределением интересна тем, что она сортирует массив, не сравнивая элементы друг с другом.

Рассмотрим сначала вырожденный случай сортировки распределением, а затем более общий.

При вырожденном распределении предполагается, что каждый элемент массива может принимать m (например, от 1 до m) фиксированных значений. Заведем массив Amount размерностью m, первоначально обнулив его. Затем для каждого i подсчитаем количество элементов массива A, равных i, и занесем это число в Amount[i]. После чего, в первые Amount[1] элементов массива A запишем 1, в следующие Amount[2] элементов массива A запишем 2 и т. д. до тех пор, пока не дойдем до конца массива A (заметим, что в то же время мы окажемся в конце массива Amount).

Теперь запишем алгоритм:

procedure DispersSort(n, m:  integer;

var A: array[1..n] of integer); {Процедура сортировки вырожденным распределением} var

i, j, k: integer; Amount: array[1..m]  of integer; begin

{Обнуляем массив Amount}

for i := 0 to m do Amount[i]   := 0;

{Заполняем массив Amount}

for i := 1 to n do Amount[A[i]] := Amount[A[i]] + 1; {Заполняем массив A} k := 1;

for i := 0 to M do

for j  := 1 to Amount[i]  do begin

A[k] := i; k := k + 1;

end;

end;

Временную сложность метода можно оценить как O(m+n) (m появляется в сумме, так как изначально надо обнулить массив Amount, а это требует m действий). Пространственная сложность в этом случае пропорциональна O(m), поскольку требуется дополнительная память размером порядка m.

Недостатком этого метода является то, что требуется дополнительная память размером порядка m, а это может оказаться недопустимым из-за большого значения m. Но, если m>>n, то имеется способ уменьшить объем требуемой дополнительной памяти, который сейчас и рассмотрим, как общий случай сортировки распределением.

Пусть выделяется дополнительная память размером b+n, а элементы массива могут принимать значения от 0 до s, причем s>>b.

Каждый элемент этого массива можно представить в b-ичной системе счисления и разбить на k цифр этой системы счисления.

Заведем списки L₁, L₂, L_b общей суммарной длиной порядка n (это можно сделать, ограничившись дополнительной памятью O(b+n)) (рис. 48).

Тогда алгоритм сортировки распределением можно представить следующим образом: for i  := k downto 1 do begin

for j   := 1 to n do begin

if p = i-й цифре A[j]  в b-й системе счисления then 
занести A[j]  в L[p]  список;

end;

Очистить массив A;

for j  := 1 to b do

Дописать элементы L[j]   в массив A; 
end;

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

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

Достигнув i = 1, получаем полностью отсортированный массив.

Как нетрудно заметить, если положить s = b, то отпадает необходимость заводить списки и производить запись в них: в j-ый список будут попадать только числа, равные j. В этом случае достаточно хранить лишь размеры списков, т. е. подсчитать количество элементов, равных j, для всех j от 1 до s. А потом просто заново заполнить массив A в соответствии с этими количествами, т. е. получаем вырожденную сортировку.

Рассмотрим на примере задачу сортировки 12 целых чисел из интервала от 0 до 99, т. е. n = 12, b = 10 (десятичная система счисления), s = =99, k = 2 (два разряда). При этом будем считать, что числа, содержащие только один разряд, дополняются слева нулем, т. е. число «0» будет «00», число «1» будет «01» и т. д.

Интересно, что временная сложность этого алгоритма пропорциональна O(hn), а если учесть, что k фактически является константой, то получаем гарантированную (минимальную, среднюю и максимальную) линейную сложность. Но недостатком этого метода является необходимость выделять дополнительную память размером порядка b + n. Если бы не это ограничение, можно было бы считать этот метод самым эффективным при больших значениях n.

2.5.2.10. Сравнение алгоритмов внутренней сортировки

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

Теоретические временные и пространственные сложности рассмотренных методов сортировки показаны в табл. 4.

Эта таблица позволяет сделать ряд выводов.

1. На небольших наборах данных целесообразнее использовать сортировку включением, так как из всех методов, имеющих очень простую программную реализацию, этот на практике оказывается самым быст-

 

 

рым и при размерностях меньше ~3000 дает вполне приемлемую для большинства случаев скорость работы. Еще одно преимущество этого метода заключается в том, что он использует полную или частичную упорядоченность входных данных и на упорядоченных данных работает быстрее, а на практике данные, как правило, уже имеют хотя бы частичный порядок.

2. Алгоритм пузырьковой сортировки, причем в той его модификации, которая не использует частичный порядок данных исходного массива, хотя и часто используется, но имеет плохие показатели даже среди простых методов с квадратичной сложностью.
3. Сортировка Шелла оказывается лишь красивым теоретическим методом, потому что на практике использовать его нецелесообразно: он сложен в реализации, но не дает такой скорости, какую дают сравнимые с ним по сложности программной реализации методы.
4. При сортировке больших массивов исходных данных лучше использовать быструю сортировку.
5. Если же добавляется требование гарантировать приемлемое время работы метода (быстрая сортировка в худшем случае имеет сложность, пропорциональную O(n²), хотя вероятность такого случая очень мала), то надо применять либо древесную сортировку, либо сортировку слиянием. Как видно из таблиц, сортировка слиянием работает быстрее, но следует помнить, что она требует дополнительную память размером порядка n.

6. В тех же случаях, когда есть возможность использовать дополнительную память размером порядка n, имеет смысл воспользоваться сортировкой распределением.

2.5.3. Алгоритмы внешней сортировки

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

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

Применение большинства алгоритмов внутренней сортировки для сортировки файлов требует порядка O(n) проходов. Однако, если несколько модифицировать алгоритм сортировки слиянием (см. п. 2.5.2.8), то можно произвести сортировку, осуществляя порядка O(log n) проходов.

Основное отличие сортировки слиянием для файлов, заключается в следующем. Вся сортируемая последовательность данных разбивается на два файла J₁ иf,. Желательно, чтобы количество записей в этих файлах было поровну. Как и в алгоритме внутренней сортировки, считаем, что любой файл состоит из участков длиной 1. Затем можно объединить участки длины 1 и распределить их по файлам g_x и g₂ в виде участков длины 2. После этого делаем fj иf пустыми и объединяем g_x и g2 в fi и J2, которые затем можно организовать в виде участков длины 4

и т. д.

После выполнения i подобного рода проходов получатся два файла, состоящие из участков длины 2¹. Если 2¹ > n, тогда один из этих двух файлов будет пустым, а другой будет содержать единственный участок длиной n, т. е. будет отсортирован. Так как 2¹ > n при i > log n, то не-

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

2.6. Алгоритмы на графах 2.6.1. Алгоритм определения циклов

Наличие циклов в графе можно определить с помощью эффективного и простого алгоритма. Алгоритм может быть реализован как для матричного, так и для спискового способа представления графа. В случае неориентированного графа его ребра считаются двунаправленными.

Принцип выделения циклов следующий. Если вершина имеет только входные или только выходные дуги, то она явно не входит ни в один цикл. Можно удалить все такие вершины из графа вместе со связанными с ними дугами. В результате появятся новые вершины, имеющие только входные или только выходные дуги. Они также удаляются. Итерации повторяются до тех пор, пока граф не перестанет изменяться.

Отсутствие изменений свидетельствует об отсутствии циклов, если все вершины были удалены. Все оставшиеся вершины обязательно принадлежат циклам (рис. 60).

Сформулируем алгоритм, используя матрицу смежности (см. 1.3.3.2):

var

M: TadjacencyMatrix; repeat

for i  := 1 to n begin

if строка M(i ,*)  = 0 then обнулить столбец M(*,  i);

if столбец M(*,  i)  = 0 then обнулить строку M(i ,*); end;

until M не изменилась;

if M нулевая then граф ациклический

else граф содержит циклы;

Достоинством данного алгоритма является то, что происходит одновременное определение цикличности или ацикличности графа и исключение дуг, не входящих в циклы. После завершения алгоритма остается матрица смежности, соответствующая подграфу, содержащему все циклы исходного графа.