![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сортировка и реверсирование с помощью рекурсии.
Рекурсия часто предлагает программы, которые эффективны и элегантны. Идея быстрой сортировки с использованием разделения и слияния может быть применена рекурсивно.
Новые идеи: рекурсивная сортировка, рекурсивное реверсирование.
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
Рекурсивное решение более ясное, чем итеративное, потому что здесь не требуется идентифицировать или отслеживать границы выполнения.
|