Сортировка и реверсирование с помощью рекурсии.

Рекурсия часто предлагает программы, которые эффективны и элегантны. Идея быстрой сортировки с использованием разделения и слияния может быть применена рекурсивно.

Новые идеи: рекурсивная сортировка, рекурсивное реверсирование.

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

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