Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 12

Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр

стр.: 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

Полный текст лекций можно скачать здесь

---

Vvod(n);

Sort(1, N);

Vivod;

ReadLn

End.

Можно реализовать сортировку Хоара и без использования рекурсии. Пары индексов (k, r), задающих границы сортировки, поместим в стек. Разделив часть массива, определенную парой из вершины стека, заменим эту пару двумя новыми парами индексов. Сначала в стеке будет пара (1, n), затем после первого разделения содержимым стека будут пары (1, j) и (i, n) и так далее. Очевидно, в стеке не может быть более n пар. В процессе сортировки некоторые части исчерпываются, что ведет к уменьшению числа элементов стека.

Разделяющий элемент массива не обязан оставаться на своем месте. Полезно проверить, что массив 60, 63, 10, 51, 24, 55, 90 после первого разделения примет порядок 24, 51, 10, 63, 60, 55, 90. Значение i будет равно 4, а j станет равным 3. Выделенные части массива определяются границами индексов (1, 3) и (4, 7).

Сортировка Хоара примерно вдвое быстрее пирамидальной сортировки. Среднее число пересылок элементов M в этом методе составляет ln2*(nlog ₂ n)/3.

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

Метод сортировки	По возрастанию	Случайно	По убыванию
Простое включение	0.22	50.74	103.80
Включение с бинарным поиском	1.16	37.66	76.06
Простой выбор	58.18	58.34	73.46
Пузырьковая	80.18	128.84	178.66
Шейкер-сортировка	0.16	104.44	187.36
Шелла	0.80	7.08	12.34
Пирамидальная	2.32	2.22	2.12
Быстрая Хоара с рекурсией	0.72	1.22	0.76
Быстрая Хоара без рекурсии	0.72	1.32	0.80
Простое слияние	1.98	2.06	1.98

6.2. Методы внешней сортировки

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

В основе методов внешней сортировки лежит процедура слияния, заключающаяся в объединении двух или более отсортированных последовательностей. Рассмотрим эту процедуру на примере слияния двух последовательностей A и B в последовательность C. Пусть элементы A и B отсортированы по возрастанию, то есть a₁  a₂  … a_m и b₁  b₂  … b_n . Требуется, чтобы последовательность C также располагалась по возрастанию, то есть выполнялось c₁  c₂  … c_m+n.

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

Можно заметить, что доступ к элементам A, B и C выполнялся строго последовательно. В методах внешней сортировки в качестве последовательностей A, B и C фигурируют отсортированные участки файлов.

Базовым методом внешней сортировки является метод простого слияния. Рассмотрим его на следующем примере. Пусть имеется файл A, включающий элементы 27, 16, 13, 11, 18, 25, 7. Этот файл разделяется на два файла B и C путем поочередной записи элементов в эти файлы. Покажем это схемой

B: 27, 13, 18, 7

A: 27, 16, 13, 11, 18, 25, 7

C: 16, 11, 25

Затем файлы B и C снова соединяются путем поочередного включения в C элементов из A и B. При этом первым располагается меньший элемент каждой пары. Получится следующий результат

B: 27, 13, 18, 7

A: 16, 27,’ 11, 13,’ 18, 25, ‘ 7

C: 16, 11, 25

Пары отделяются друг от друга апострофами. На следующем этапе снова происходит разделение файла A на B и C, но в каждый файл пишутся поочередно уже не отдельные элементы, а выделенные пары. Получаем

B: 16, 27,’ 18, 25

A: 16, 27,’ 11, 13,’ 18, 25, ‘ 7

C: 11, 13,’ 7

Далее происходит соединение пар в упорядоченные четверки путем использования процедуры слияния

B: 16, 27,’ 18, 25

A: 11, 13, 16, 27,’ 7, 18, 25

C: 11, 13,’ 7

Затем файл A распределяется по четверкам элементов и при новом соединении будет состоять из упорядоченных восьмерок элементов. В нашем примере сортировка закончится на этом этапе. В общем случае длина отсортированных серий будет увеличиваться по степеням 2, пока величина серии не превзойдет количество элементов в файле.

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

Есть очевидное усовершенствование метода. Результат слияния сразу распределяется на две ленты, то есть в процессе участвуют уже 4 ленты. За счет дополнительной памяти число операций перезаписи уменьшается вдвое. Это однофазный четырехленточный метод, называемый также сбалансированным слиянием.

Как видно из приведенных выше данных, метод может конкурировать по скорости с самыми быстрыми методами внутренней сортировки, но не применяется в таком качестве, так как требует значительных затрат памяти. Число проходов оценивается величиной log ₂ n, а общее число пересылок M пропорцинально n log ₂ n.

Метод простого слияния не дает какого-либо выигрыша в тех случаях, когда файл A полностью либо частично отсортирован. Этот недостаток отсутствует в методе естественного слияния.

Назовем серией последовательность элементов a_i, a_i+1, …, a_j, удовлетворяющих соотношениям a_i-1 > a_i  a_i+1  … a_j > a_j+1. В частных случаях серия может находиться в начале или конце последовательности.

Исходный файл A разбивается на серии. Распределение на B и C ведется по сериям. При соединении сливаются пары серий. Снова возможен как трехленточный, так и четырехленточный вариант метода. Ниже показан пример сортировки методом естественного слияния c 4 лентами.

B: 17, 25, 41, ‘6

A: 17, 25, 41, ‘ 9, 11, ‘ 6, ‘ 3, 5, 8, 44

C: 9, 11, ‘ 3, 5, 8, 44

A: 9, 11, 17, 25, 41 B: 3, 5, 6, 8, 9, 11, 17, 25, 41, 44

D: 3, 5, 6, 8, 44 C:

При последнем разделении лента C оказывается пустой, и отсортированный файл остается на ленте B.

Метод естественного слияния в целом быстрее, но требует большего числа сравнений, так как требуется определять конец каждой серии. Ниже приведена программа сортировки файла двухфазным трехленточным методом естественного слияния.

Program SortSlian;

{ 3-ленточная, 2-фазная сортировка естественным слиянием }

{ ключи целые и положительные }

Uses Crt;

Type

elem=record

Key: integer;

{ другие поля }

end;

tape=file of elem;

Var

Name: string[30]; { имя исходного файла }

A, B, C: tape;

K, L: integer;

S, T: elem;

e: boolean;

Procedure Vvod(var F: tape);

Begin

Rewrite(F);

K:=1;

While K <> -1 do

begin

Write('Введите очередной ключ (конец -1): ');

Read(K);

S.Key:=K;

if K<>-1 then Write(F, S)

end;

ReadLn;

Close(F)

End;

Procedure Pech(var F: tape);

Begin

Reset(F);

While not eof(F) do

begin

Read(F, S);

Write(S. Key,' ')

end;

WriteLn

End;

Procedure CopyElem(var X, Y: tape;

var Buf: elem; var E: boolean);

{ копирование элемента и считывание следующего }

{ в Buf с проверкой конца серии (E=True) }

Begin

K:=Buf.Key;

Write(Y, Buf);

if not Eof(X) then Read(X, Buf)

else Buf.Key:=-1; { барьер: достигнут конец файла }

E:=(Buf.Key<K) { E=True в конце серии }

End;

Procedure CopySer(var X, Y: tape; var Buf: elem);

{ копирование серии из X в Y }

{ в начале Buf-первый элемент текущей серии на X }

{ в конце Buf-первый элемент следующей или –1 (конец X) }

Begin

if Buf.Key>0 then { файл X не считан }

Repeat

CopyElem(X, Y, Buf, E)

Until E { E=True в конце серии }

End;

Procedure Raspred;

{ распределение A ---> B и C }

Begin

Reset(A);

Read(A, S); { первый элемент из A }

Rewrite(B);

Rewrite(C);

Repeat

CopySer(A, B, S); { S-первый элемент следующей серии }

if S.Key>0 then { файл A скопирован не весь }

CopySer(A, C, S)

Until S.Key<0

End;

Procedure Slian;

{ слияние B и C--->A }

Var

E1, E2: boolean;

Procedure SlianSer;

{ слияние серий из B и C ---> A }

{ S и T - первые элементы серий }

{ S.Key<0-весь файл B считан, T.Key<0-файл C считан }

Begin

Repeat

E1:=False;

E2:=False;

if (S.Key>0) and ((S.Key<T.Key) or (T.Key<0)) then

{ файл B не считан и текущий элемент B меньше, чем в C }

{ либо файл C полностью считан }

begin

CopyElem(B, A, S, E1);

if E1 then { достигнут конец серии на B }

CopySer(C, A, T)

end

else

begin

CopyElem(C, A, T, E2);

if E2 then { достигнут конец серии на C }

CopySer(B, A, S)

end

Until E1 or E2

End;

Begin { начало Slian }

Reset(B);

Reset(C);

if not (Eof(B) or Eof(C)) then

begin { оба файла не пусты }

Rewrite(A);

Read(B, S);

Read(C, T);

L:=0; { счетчик числа серий }

While (S.Key>0) or (T.Key>0) do

begin

SlianSer;

L:=L+1

end

end

End;

Begin { начало основной программы }

ClrScr;

Write('Введите имя файла для записи элементов: ');

ReadLn(name);

Assign(A, Name);

Assign(B, 'Rab1');

Assign(C, 'Rab2');

Vvod(A);

L:=0; { L - число серий после слияния - параметр }

Repeat

WriteLn('Файл A: '); Pech(A);

Raspred; { фаза распределения }

WriteLn('Файл B: '); Pech(B);

WriteLn('Файл C: '); Pech(C);

ReadLn; { пауза }

Slian { фаза слияния }

Until L<=1; { L=0, если исходный файл отсортирован }

WriteLn('Файл A в конце: ');

Pech(A);

Close(A);

Close(B); Erase(B); { удаление рабочих файлов }

Close(C); Erase(C);

ReadLn

End.

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