Читайте также:
|
Рекурсия часто предлагает программы, которые эффективны и элегантны. Идея быстрой сортировки с использованием разделения и слияния может быть применена рекурсивно.
Новые идеи: рекурсивная сортировка, рекурсивное реверсирование.
RSort сортирует используя идею повторяющегося выбора, реализованную итеративно в SelectSort. Однако MergeSort – значительно более быстрая итеративная сортировка чем SelectSort. Существует ли рекурсивный вариант MergeSort?
Чтобы применять рекурсию эффективно, сортируемая строка должна быть разделена, скажем, наполовину. Если половинки по отдельности отсортированы, они могут быть слиты, как показано в примере:
Исходная строка:
†character†
Разбиваем на две примерно равные строки:
†chara† †cter†
Сортируем полустроки
†aachr† †cert†
Сливаем полустроки в сортированную строку
†aaccehrrt†
Рекурсия происходит на втором шаге: та же процедура может быть использована для сортировки полустрок, какая применялась ранее для сортировки целой.
Остается только найти способ разделить файл на половинки. Один из известных нам способов разделения файла на две половинки – это деление на четные и нечетные. В данном случае нам не важно, какие именно символы оказались в той или иной части, важно, чтобы половинки были примерно равной длины.
Для примера, рассмотренного выше, половинки, полученные разбиением на четные и нечетные, будут:
†caatr† †hrce†
Сортируем полустроки
†aacrt† †cehr†
Сливаем полустроки в сортированную строку
†aaccehrrt†
В предыдущем и данном случае полустроки разные, но результат одинаковый.
Каждая рекурсия будет сортировать файл, который будет не больше половины длины, того, что обрабатывался на предыдущем шаге. Наконец, это деление произведет файл размером в один символ, который уже отсортирован. Таким образом, рекурсия будет завершаться проверкой длины файла.
Эти идеи приводят нас к следующему проекту быстрой рекурсивной сортировки
Раздел проекта 1 [DP 1]
PROCEDURE RecursiveSort(VAR F1: TEXT);
VAR
F2, F3: TEXT;
Ch: CHAR;
{PROCEDURE Split(VAR F1, F2, F3: TEXT)
Разбивает F1 на F2 и F3}
{PROCEDURE Merge(VAR F1, F2, F3: TEXT)
Сливает F2 и F3 в F1}
BEGIN {RecursiveSort}
RESET(F1);
IF NOT (EOLN(F1))
THEN
BEGIN
IF NOT (EOLN(F1))
THEN {Файл имеет как минимум 2 символа}
BEGIN
Split(F1, F2, F3);
RecursiveSort(F2);
RecursiveSort(F3);
Merge(F1, F2, F3);
END
END
END {RecursiveSort}
Раздел проекта 1.1 [DP 1.1]
PROCEDURE Split(VAR F1, F2, F3: TEXT);
{Разбивает F1 на F2, F3}
VAR
Ch, Switch: CHAR;
BEGIN {Split}
RESET(F1);
REWRITE(F2);
REWRITE(F3);
{Копировать F1 попеременно в F2 и F3}
WRITELN(F2);
WRITELN(F3);
END {Split}
Раздел проекта 1.1.1 [DP 1.1.1]
BEGIN {Копировать F1 попеременно в F2 и F3}
Switch:= '2';
WHILE NOT (EOLN(F1))
DO
BEGIN
READ(F1, Ch);
IF (Switch = '2')
THEN
BEGIN
WRITE(F2, Ch);
Switch:= '3';
END
ELSE
BEGIN
WRITE(F3, Ch);
Switch:= '2';
END
END
END
Раздел проекта 1.2 [DP 1.2]
PROCEDURE Merge(VAR F1, F2, F3: TEXT);
{Сливает F2, F3 в F1 в сортированном порядке}
VAR
Ch2, Ch3: CHAR;
BEGIN {Merge}
RESET(F2);
RESET(F3);
REWRITE(F1);
READ(F2, Ch2);
READ(F3, Ch3);
WHILE (NOT(EOF(F2))) AND (NOT(EOF(F3))))
DO
BEGIN
IF Ch2 < CH3
THEN
BEGIN
WRITE(F1, Ch2);
READ(F2, Ch2);
END
ELSE
BEGIN
WRITE(F1, Ch3);
READ(F3, Ch3);
END
END
{Копировать остаток F2 в F1}
{Копировать остаток F3 в F1}
WRITELN(F1);
END {Merge}
Раздел проекта 1.2.1 [DP 1.2.1]
BEGIN {Копировать остаток F2 в F1}
WHILE NOT (EOF(F2))
DO
BEGIN
WRITE(F1, Ch2);
READ(F2, Ch2);
END
END
Раздел проекта 1.2.2 [DP 1.2.2]
BEGIN {Копировать остаток F3 в F1}
WHILE NOT (EOF(F3))
DO
BEGIN
WRITE(F1, Ch3);
READ(F3, Ch3);
END
END
Рекурсивное решение более ясное, чем итеративное, потому что здесь не требуется идентифицировать или отслеживать границы выполнения.
Дата добавления: 2015-04-12; просмотров: 87 | Поможем написать вашу работу | Нарушение авторских прав |