Программа SelectSort

Сортировка строки символов с помощью набора выражений IF, использовавшаяся ранее требует программу, которая растет с размером сортируемой строк и требует тем больше переменных, чем больше строка. Теперь может быть разработана простая программа которая может сортировать строки любой длины. Сортируемая строка сохраняется в текстовом файле используя только одну переменную вне зависимости от того какой длины строка. Идея MinSort – найти и записать минимальную переменную в строке, минимальную переменную остатка строки и т.д. до тех пор пока вся строка не будет выведена. Это будет работать, если мы сможем копировать один файл в другой параллельно с нахождением минимума и многократно использовать созданный промежуточный файл с исключенным найденным минимальным символом.

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

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

{Копировать INPUT в F1 }

WHILE {в F1 имеются данные}

DO

BEGIN

{Печатать минимальный из F1}

{Копировать остальные из F1 в F2}

{Копировать F2 в F1}

END

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

Вот проект, основанный на этих идеях:

DP 3

PROGRAM SelectSort (INPUT, OUTPUT);

{Сортирует символы, предшествующие # из INPUT в OUTPUT.

Программа выдаст ошибку, если в INPUT отсутствует #}

VAR

Ch, Min: CHAR;

F1, F2: TEXT;

BEGIN {SelectSort}

{Копировать INPUT в F1 и эхо в OUTPUT}

{Сортировать F1 в OUTPUT используя стратегию SelectSort}

END. {SelectSort}

DP 3.1

BEGIN {Копировать INPUT в F1 и эхо в OUTPUT}

REWRITE(F1);

WRITE(OUTPUT, ‘INPUT DATA:’);

READ(INPUT, Ch);

WHILE Ch <> ‘#’

DO

BEGIN

WRITE(F1, Ch);

WRITE(OUTPUT, Ch);

READ(INPUT, Ch)

END;

WRITELN(OUTPUT);

WRITELN(F1, ‘#’)

END

DP 3.2

BEGIN {Сортировать F1 в OUTPUT используя стратегию SelectSort}

WRITE(OUTPUT, ‘SORTED DATA:’);

RESET(F1);

READ(F1, Ch);

WHILE Ch <> ‘#’

DO { Ch <> ‘#’ и Ch1 – первый символ F1}

BEGIN

{Выбираем минимальный из F1 b копируем остаток F1 в F2}

WRITE(OUTPUT, Min);

{Копируем F2 в F1}

RESET(F1);

READ(F1, Ch)

END;

WRITELN(OUTPUT);

END

Комментарий состояния (суждение) в части DO

{ Ch <> ‘#’ и Ch1 – первый символ F1}

в DP 3.2 будет необходим в DP 3.2.1, которая реализует первую подзадачу в операторе BEGIN части DO. Первая часть суждения в части DO является TRUE, потому что Ch <> ‘#’ является условием выполнения части DO. Вторая часть суждения является TRUE, потому что эта точка может быть достигнута либо сверху, либо после успешного выполнения цикла, в любом случае последние два выполненных оператора будут:

RESET(F1);

READ(F1, Ch)

Таким образом, Ch должна содержать первый символ F1. Без этого анализа было бы трудно предположить, какое начальное значение присвоить Min в 3.2.1.

DP 3.2.1

BEGIN {Выбираем минимальный из F1 b копируем остаток F1 в F2}

REWRITE(F2);

Min := Ch;

READ(F1, Ch);

WHILE Ch <> ‘#’

DO { Ch <> ‘#’ и Ch1 – первый символ F1}

BEGIN

{Выбираем минимальный из (Ch, Min)

копируем второй символ в F2}

READ(F1, Ch)

END;

WRITELN(F2, ‘#’);

END

DP 3.2.2

BEGIN {Копируем F2 в F1}

RESET(F2);

REWRITE(F1);

READ(F2, Ch);

WHILE Ch <> ‘#’

DO

BEGIN

WRITE(F1, Ch);

READ(F2, Ch)

END;

WRITELN(F1, ‘#’);

END

DP 3.2.1.1

BEGIN {Выбираем минимальный из (Ch, Min)

копируем второй символ в F2}

IF Ch < Min

THEN {Ch – минимальный из (Ch, Min)}

BEGIN

WRITE(F2, Min);

Min := Ch;

END

ELSE {Min – минимальный из (Ch, Min)}

WRITE(F2, Ch);

END

Для того, чтобы достичь уверенности в DP 3.2 мы седлаем 4 частичных таблицы выполнения для ее поведения (исключая начальные выражения WRITE для аннотированного вывода). Эти таблицы исследуют варианты, в которых в F1 отсутствуют символы кроме #, когда в F1 один символ и когда в F1 два символа сортированные и нет. В каждом случае Min присваивается минимальный из двух символов из F1 и остальные символы копируются в F2.

Таблица выполнения для DP 3.2, символы в F1 отсутствуют

Таблица выполнения для DP 3.2, в F1 один символ

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

В строку финальных значений

Изучая таблицу можно сделать вывод, что единственный символ в F1 присваивается Min и добавляется в OUTPUT вне зависимости от изначальных значений F2, Ch и Min.

Таблица выполнения для DP 3.2, в F1 два символа в обратном порядке

DP 3.2.2 в этой таблице выполнения был пропущен.

Когда выполнение достигает строчки RESET(F1) минимальное значение из F1 добавляется к OUTPUT и оставшаяся задача сокращается к сортировке файла с одним символом как в предыдущей таблице. Поскольку значения F2, Ch и Min в данном случае несущественны, единственный символ в F1 (в данный момент C) присваивается Min и добавляется к OUTPUT. Поэтому уже на этом этапе мы можем предположить, что таблица выполнения для этого случая будет завершена следующей комбинацией:

Что собственно и выяснилось при завершении таблицы выполнения.

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

Таблица выполнения для DP 3.2, в F1 два символа в обратном порядке

Варианты, показанные в пяти таблицах выполнения, позволяют нам спрогнозировать варианты, когда F1 содержит более 2 символов. На каждом шаге минимальный из F1 помещается в Min, и остаток копируется в F2. Если это символ встречается в F2 несколько раз, то только первый помещается в Min. Другие вхождения этого символа копируются в F2 вместе с остальными.

Для поддержки анализа SelectSort может быть собрана для тестирования. Возможно проект не слишком большой для того, чтобы собрать все сразу, но идея сначала собрать части 3, 3.1, 3.2, 3.2.1 нам кажется более удачной. Раздел 3.2.2 заменим выражением, которое выводит единственный символ # в F1, в результате чего будет выполняться только одна итерация.

DP 3A

PROGRAM SelectSort (INPUT, OUTPUT);

{Сортирует символы, предшествующие # из INPUT в OUTPUT.

Программа выдаст ошибку, если в INPUT отсутствует #}

VAR

Ch, Min: CHAR;

F1, F2: TEXT;

BEGIN {SelectSort}

BEGIN {Копировать INPUT в F1 и эхо в OUTPUT}

REWRITE(F1);

WRITE(OUTPUT, 'INPUT DATA:');

READ(INPUT, Ch);

WHILE Ch <> '#'

DO

BEGIN

WRITE(F1, Ch);

WRITE(OUTPUT, Ch);

READ(INPUT, Ch)

END;

WRITELN(OUTPUT);

WRITELN(F1, '#')

END

BEGIN {Сортировать F1 в OUTPUT используя стратегию SelectSort}

WRITE(OUTPUT, 'SORTED DATA:');

RESET(F1);

READ(F1, Ch);

WHILE Ch <> '#'

DO { Ch <> '#' и Ch1 - первый символ F1}

BEGIN

BEGIN {Выбираем минимальный из F1, копируем остаток F1 в F2}

REWRITE(F2);

Min := Ch;

READ(F1, Ch);

WHILE Ch <> '#'

DO { Ch <> '#' и Ch1 - первый символ F1}

BEGIN

{Выбираем минимальный из (Ch, Min)

копируем второй символ в F2}

READ(F1, Ch)

END;

WRITELN(F2, '#');

END

WRITE(OUTPUT, Min);

{Для тестирования создаем пустой F1}

REWRITE(F1);

WRITELN(F1, ‘#’);

{вместо …}

{Копируем F2 в F1}

RESET(F1);

READ(F1, Ch)

END;

WRITELN(OUTPUT);

END

END. {SelectSort}

Выполнение:

INPUT: XBZA#

OUTPUT: INPUT DATA:XBZA#

SORTED DATA:X

Тест работает как и ожидалось: первый символ из INPUT помещается в OUTPUT, как будто в файле он один.

Когда мы соберем программу полностью, нам останется протестировать код находящий минимум и копирующий файлы. Если была проблема в предыдущем коде, она должна проявиться при выводе сортированной последовательности в OUTPUT.

Поскольку содержимое промежуточных фалов пропадает, имеет смысл распечатывать его чтобы упростить тестирование.

DP 3B

PROGRAM SelectSort (INPUT, OUTPUT);

{Сортирует символы, предшествующие # из INPUT в OUTPUT.

Программа выдаст ошибку, если в INPUT отсутствует #}

VAR

Ch, Min: CHAR;

F1, F2: TEXT;

BEGIN {SelectSort}

BEGIN {Копировать INPUT в F1 и эхо в OUTPUT}

REWRITE(F1);

WRITE(OUTPUT, 'INPUT DATA:');

READ(INPUT, Ch);

WHILE Ch <> '#'

DO

BEGIN

WRITE(F1, Ch);

WRITE(OUTPUT, Ch);

READ(INPUT, Ch)

END;

WRITELN(OUTPUT);

WRITELN(F1, '#')

END

BEGIN {Сортировать F1 в OUTPUT используя стратегию SelectSort}

WRITE(OUTPUT, 'SORTED DATA:');

RESET(F1);

READ(F1, Ch);

WHILE Ch <> '#'

DO { Ch <> '#' и Ch1 - первый символ F1}

BEGIN

BEGIN {Выбираем минимальный из F1, копируем остаток F1 в F2}

REWRITE(F2);

Min := Ch;

READ(F1, Ch);

WHILE Ch <> '#'

DO { Ch <> '#' и Ch1 - первый символ F1}

BEGIN

BEGIN {Выбираем минимальный из (Ch, Min)

копируем второй символ в F2}

IF Ch < Min

THEN {Ch - минимальный из (Ch, Min)}

BEGIN

WRITE(F2, Min);

Min := Ch;

END

ELSE {Min - минимальный из (Ch, Min)}

WRITE(F2, Ch);

END;

READ(F1, Ch)

END;

WRITELN(F2, '#');

END

WRITE(OUTPUT, Min);

BEGIN {Копируем F2 в F1}

RESET(F2);

REWRITE(F1);

READ(F2, Ch);

WHILE Ch <> '#'

DO

BEGIN

WRITE(Ch) {Тестирование}

WRITE(F1, Ch);

READ(F2, Ch)

END;

WRITELN('#(F1)'); {Тестирование}

WRITELN(F1, '#');

END

RESET(F1);

READ(F1, Ch)

END;

WRITELN(OUTPUT);

END

END. {SelectSort}

Выполнение:

INPUT: CEDAR#

OUTPUT: INPUT DATA: CEDAR #

SORTED DATA: A(Min) EDCR#(F1)

C(Min) EDR#(F1)

D(Min) ER#(F1)

E(Min) R#(F1)

R(Min) #(F1)

Этот тест показывает что поиск минимума и копирование работает так как и ожидалось. Первая строка показывает, что текущим найденным минимумом является A, на следующем проходе он сменяется на C и т.д.

Конечная версия программы SelectSort получается удалением отладочных операторов WRITE из DP 3B.

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