Cхемы сортировки, страница 4

(Подразумевается использование оператора GOTO)

Сортировка естественным двухпутевым слиянием.

Рис. 5 иллюстрирует сортировку слиянием, когда мы продвигаемся с обоих концов, подобно методам быстрой сортировки, обменной сортировки и т.д. Мы анализируем исходный файл слева и справа, двигаясь к середине. Пропустим первую строку и рассмотрим вторую. Слева мы видим возрастающий отрезок 503 703 765, а справа, если читать справа налево, имеем отрезок 087 512 677. Слияние этих двух последовательностей дает подфайл 087 503 512 677 703 765, который перемещается слева в строке 3. Затем ключи 061 612 908 в строке 2 сливаются с 170 509 987 и результат записывается справа в строке 3. Наконец, 154 275 426 653 сливается с 653 (перекрытие обнаруживается раньше, чем оно может привести к нежелательным последствиям) и результат записывается слева. Точно также строка 2 получилась из исходного файла в строке 1.

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

Описанный метод называют "естественным" слиянием, потому что он использует отрезки, которые "естественно" образуются в файле.

Алгоритм Е (Сортировка естественным двухпутевым слиянием).

При сортировке записей R₁, …, R_N используются две области памяти, каждая из которых может содержать N записей. Для удобства обозначим записи, находящиеся во второй области, через R_N+1, …, R_2N, хотя в действительности области не обязательно идти друг за другом. Начальное содержание второй области не имеет значение. После завершения алгоритма ключи будут упорядочены К₁  … К_N.

Блок-схема, построенная в соответствии

с принципами структурного программирования

1. (Начальная установка) Установить s:=0 (при s=0 мы будем пересылать записи из области (R₁,…R_N) в область (R_N+1, …, R_2N); при s=1 наоборот.)

2. (Подготовиться к просмотру) Если s=0, то установить i:=1, j:=N, k:=N+1, g:=2N, если s=1, то установить i:=N+1, j:=2N, k:=1, g:=N. (переменные i, j, k, g указывают текущие позиции во входных "файлах", откуда идет чтение, и в "выходных" файлах, куда идет запись; i и k – левые позиции, j и r – правые позиции.) Установить d:=1, f:=1 (Переменные d определяет текущее направление вывода, f устанавливается равной 0, если необходимы дальнейшие просмотры.)

3. (Сравнения К_i с К_j) Если К_i  К_j, то перейти к шагу Е8, если i=j (т.е. рассматриваем один и тот же элемент с разных концов), то установить R_k:=R_i и перейти к шагу Е13.

4. (Пересылка R_i) (Шаги Е4-Е7 аналогичны шагам М3-М4 алгоритма М). Установить R_k:=R_i, k:=k+d.

5. (Ступенька вниз?) Увеличить i на 1, Затем, если К_i–1  К_i, то возвратиться к шагу Е3.

6. (Пересылка R_j) Установить R_k:=R_j, k:=k+d.

7. (Ступенька вниз?). Уменьшить j на 1. Затем, если К_j+1  К_j, то возвратиться к шагу Е6, в противном случае перейти к шагу Е12.

8. (Пересылка R_j) (Шаги Е8–Е11 двойственные по отношению к шагам Е4–Е7) Установить R_k:=R_j, k:=k+d.

9. (Ступенька вниз?). Уменьшить j на 1. Затем, если К_j+1  К_j, то возвратиться к шагу Е3

10. (Пересылка R_j) Установить R_k:=R_i, k:=k+d.

11. (Ступенька вниз?). Увеличить i на 1, Затем, если К_i–1  К_i, то возвратиться к шагу Е10.

12. (Переключение направления). Установить f:=0, d:= – d и взаимозаменить k - g. Возвратиться к шагу Е3.

13. (Переключение областей) Если f=0, то установить s:=1–s и возвратиться к шагу Е2, в противном случае сортировка завершена, если s=0, то установить (R₁,…R_N) := (R_N+1, …, R_2N) (если это критично).

Если исходный файл случаен, то в нем около 1/2N возрастающих отрезков, так как К_i  К_i+1 с вероятностью 1/2. При каждом просмотре число отрезков сокращается вдвое. Число просмотров, как правило, составляет около lоg₂ N. При каждом просмотре мы должны переписать все N записей, и большая часть времени затрачивается в шагах Е3, Е4, Е5, Е8, Е9. Общее время работы асимптотически приближается к 12.5Nlоg₂N, как в среднем, так и худшем варианте. Это медленнее быстрой сортировки и не настолько лучше пирамидальной сортировки (16lоg₂N), чтобы оправдать вдвое больший расход памяти.

Сортировка простым (фиксированным) двухпутевым слиянием.

В алгоритме Е границы между отрезками полностью определяются "ступеньками вниз". Такой подход обладает тем возможным преимуществом, что исходные файлы с преобладанием возрастающего или убывающего расположения элементов могут обрабатываться очень быстро, но при этом замедляется основной цикл вычислений. Вместо проверок ступенек вниз можно принудительно установить длину отрезков, считая, что все отрезки исходного файла имеют длину 1, после первого просмотра все отрезки (кроме, быть может, последнего) имеют длину 2, …, после k^го просмотра имеют длину 2^k. В отличие от "естественного" слияния в алгоритме Е такой способ называется простым (или фиксированным) двухпутевым слиянием.

Пример работы алгоритма Ф приведен на Рис. 6. Этот метод справедлив и тогда, когда N не является степенью 2, сливаемые отрезки не все имеют длину 2^k. Проверки ступенек заменены уменьшением длины переменных q и r и проверкой на равенство нулю. Благодаря этому время асимптотически приближается к 11Nlоg₂N, что несколько лучше, чем в предыдущем алгоритме.

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

Рис. 6 Сортировак простым двухпутевым слиянием

Алгоритм Ф (Сортировка простым двухпутевым слиянием).

При сортировке записей R₁, …, R_N используются две области памяти, каждая из которых может содержать N записей. Для удобства обозначим записи, находящиеся во второй области, через R_N+1, …, R_2N, хотя в действительности области не обязательно идти друг за другом. Начальное содержание второй области не имеет значение. После завершения алгоритма ключи будут упорядочены К₁  … К_N.

1. (Начальная установка) Установить s:=0, (при s=0 мы будем пересылать записи из области (R₁,…R_N) в область (R_N+1, …, R_2N); при s=1 наоборот.) p:=1 (p – размер возрастающих отрезков, которые будут сливаться во время текущего просмотра; q и r – количества неслитых элементов в отрезках) (переменные i, j, k, g указывают текущие позиции во входных "файлах", откуда идет чтение, и в "выходных" файлах, куда идет запись)

2. (Подготовиться к просмотру) Если s=0, то установить i:=1, j:=N, k:=N+1, g:=2N, если s=1, то установить i:=N+1, j:=2N, k:=1, g:=N. Затем установить d:=1, q:=p, r:=p.

3. (Сравнения К_i с К_j) Если К_i  К_j, то перейти к шагу Ф8.

4. (Пересылка R_i) Установить k:=k+d, R_k:=R_i.

5. (Конец отрезка?) Установить i:=i+1, q:=q–1. Если q  0, то возвратиться к шагу Ф3.

6. (Пересылка R_j) Установить k:=k+d. Если k=g, то перейти к шагу Ф13; в противном случае установитьR_k:=R_j.

7. (Конец отрезка?) Установить j:=j–1, r:=r–1. Если r  0, то возвратиться к шагу Ф6; в противном случае перейти к шагу Ф12.

8. (Пересылка R_j) Установить k:=k+d, R_k:=R_j.

9. (Конец отрезка?) Установить j:=j–1, r:=r–1. Если r  0, то возвратиться к шагу Ф3.

10. (Пересылка R_i) Установить k:=k+d, Если k=g, то перейти к шагу Ф13; в противном случае установить R_k:=R_i.

11. (Конец отрезка?) Установить i:=i+1, q:=q–1. Если q  0, то возвратиться к шагу Ф10

12. (Переключение направления) Установить q:=p, r:=p, d:= –d и взаимозаменить k:=g. Возвратиться к шагу Ф3.

13. (Переключение областей) Установить p:=p+p. Если p  N, то установить s:=1 – s и возвратиться к шагу Ф2. В противном случае сортировка завершена; Если s=0, то установить (R₁,…R_N) := (R_N+1, …, R_2N). (Независимо от распределения исходного файла последнее копирование будет выполнено тогда и только тогда, когда значение round(log₂N) нечетно. Так что можно заранее предсказать положение отсортированного файла, и копирование, как правило, не требуется).