Работа со строками слов (стр. 5 )

  {разделить n символов в Txt на n серий единичной длины, разделенные символом ‘#’};

  WHILE Sorted = ‘N’

  DO

  BEGIN

  {разделить n/k серий длины k из Txt в n/2k серий в файлах Temp1 и Temp2};

  {соединить n/2k серий длины k из файлов Temp1 и Temp2 в n/2k серий длины 2k в файл Txt};

  {присвоить переменной Sorted значение ‘Y’ если файл Txt отсортирован, иначе присвоить ‘N’};

  END

END {MergeSort1}

10.2.2 Слияние серий.

Когда количество серий нечетно, он не могут быть просто разделен на 2 файла, например, rw#ac#ot# разделяется на rw#ot# и ac#. Таким образом, во время слияния после того, как один разделенный файл буд полностью считан, другой еще может содержать одну серию, которая должна быть скопирована в в объединенный файл без каких-либо сравнений.

Раздел проекта

{соединить n/2k серий длины k из файлов Temp1 и Temp2 в n/2k серий длины 2k в файл Txt};

будет спроектирован как вызов процедуры

MergeRuns(Temp1, Temp2, Txt)

объявленной как:

Design Part 2.1

PROCEDURE MergeRuns(VAR In1, In2, Result: TEXT);

{склеивает серии из In1 и In2 в Result }

VAR

  Ch1, Ch2: CHAR;

BEGIN {MergeRuns}

  {инициализируем параметры файлов}

  WHILE NOT EOLN(In1) AND NOT EOLN(In2)

  DO

  BEGIN

  {склеиваем серии из In1 и In2 в Result}

  END

  {копируем последнюю серию из In1 или In2 (если такая имеется) в Result};

  {сбрасываем параметры файлов}

END{MergeRuns}

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

Design Part 2.1.1

BEGIN {копируем серии из In1 и In2 в Result}

  READ(In1, Ch1);

  READ(In2, Ch2);

  WHILE (Ch1 <> ‘#’) AND (Ch2 <> ‘#’)

  DO

  {копируем меньший символ из Ch1 и Сh2 в Result и считываем

  следующий символ из соответствующего файла};

  {копируем остаток серии In1};

  {копируем остаток серии In2};

  WRITE(Result, ‘#’)

END

Design Part 2.1.2

BEGIN {копируем последнюю серию из In1 или In2 (если такая имеется) в Result}

  IF EOLN(In1) AND EOLN(In2)

  THEN

  WRITELN(In1);

  ELSE

  IF NOT EOLN(In1)

  THEN {копируем оставшуюся серию из In1 (если такая имеется) в Result}

  CopyOpen(In1, Result)

  ELSE {копируем оставшуюся серию из In2 (если такая имеется) в Result}

  CopyOpen(In2, Result)

END

10.2.3 Разделение серий.

Процедура также скрывает детали разделения одного файла на два. Часть

{разделить n/k серий длины k из Txt в n/2k серий в файлах Temp1 и Temp2}

будет спроектирована как  оператор вызова процедуры

SplitIntoRuns(Txt, Temp1, Temp2)

Design Part 2.2

PROCEDURE SplitIntoRuns(VAR FileIn, Result1, Result2: TEXT)

{разделяем серии из FileIn в серии в каждом из файлов Result1 и Result2}

VAR

  Switch, Ch: CHAR;

BEGIN {SplitIntoRuns}

  RESET(FileIn);

  REWRITE(Result1);

  REWRITE(Result2);

  {копируем серии попеременно в Result1 и Result2}

  WRITELN(Result1);

  RESET(Result1);

  WRITELN(Result2);

  RESET(Result2)

END {SplitIntoRuns}

Процедура SplitIntoRuns требует 2 символьные переменные: Ch для копирования символов и Switch для запоминания файла, в который происходит копирование в настоящий момент.

Design Part 2.2.1

BEGIN {копируем серии попеременно в Result1 и Result2}

  Switch := ‘1’;

  WHILE NOT EOLN(FileIn)

  DO

  BEGIN

  Read(FileIn, Ch);

  {копируем Ch в Result1, если Switch=’1’, иначе – в Result2}

  {Если встречен конец серии (Ch = ‘#’), то переключаем Switch на другой файл}

  END

END

10.2.4 Завершение MergeSort1

Склеенный файл проверяется в двух местах программы, для того, чтобы определить, является он отсортированным или нет, поэтому эта проверка является естественным кандидатом для оформления в виде оператора процедуры:

{присвоить переменной Sorted значение ‘Y’ если Txt отсортирован, иначе - ‘N’}

будет оформлено в

CheckIfSorted(Txt, Sorted)

Процедура CheckIfSorted устанавливает Sorted в ‘Y’, если в файле существует только одна серия (т. е. если за первым встреченным символом # сразу же следует символ конца строки).

Design Part 2.3

PROCEDURE CheckIfSorted(VAR FileIn: TEXT; VAR Sorted: Char);

{присвоить переменной Sorted значение ‘Y’ если Txt отсортирован, иначе - ‘N’}

VAR

  Ch, EndRun: CHAR;

BEGIN {CheckIfSorted}

  RESET(FileIn);

  IF EOLN(FileIn)

  THEN {пустой файл отсортирован по определению}

  Sorted := ‘Y’

  ELSE

  {установить Sorted=’Y’, если в файле есть всего одна серия, и ‘N’ в противном случае}

END {CheckIfSorted}

И, наконец, для того, чтобы начать процесс разделения-слияния, Txt разделяется на односимвольные серии, разделенные символом #. С этой целью мы добавляем новую переменную Ch символьного типа к локальным переменным процедуры MergeSort1.

Design Part 2.4

BEGIN {разделить n символов в Txt на n серий единичной длины, разделенные символом ‘#’}

  ...

END

На этом процедура MergeSort1 будет закончена.

Задание 13. Проведите сборку процедуры MergeSort1, написав самостоятельно недостающие разделы проекта.

(20 баллов)

Задание 14. Составьте набор тестовых данных, которые бы структурными тестами следующих частей программы:

       а) MergeRuns

       б) SplitIntoRuns

       в) CheckIfSorted

       г) MergeSort1

(10 баллов за каждое подзадание)

Задание 15. Часть г) предыдущего упражнения включает в себя все остальные части. Какое преимущество в тестировании их по отдельности, если, в конце концов, они будут протестированы вместе?

(10 баллов)

Задание 16. Дайте формальное доказательство того, что CheckIfSorted делает то, что должна делать.

(20 баллов)

Задание 18. Рассмотрите разделение и слияние серий на три файла вместо двух.

а) Объясните, как процедура, подобная MergeSort1 будет сортировать с использованием трех файлов.

б) Объясните, почему такая сортировка будет быстрее, показав на примере.

в) Повторите пункт b) для четырех файлов.

(15 баллов за каждое подзадание)

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

(40 баллов)

Задание 20. Модифицируйте MergeSort1 таким образом, чтобы получить преимущество от серий, существующих в изначальной строке еще до сортировки, и от серий, которые могут случайно образоваться во время каждой склейки. Как может это помочь при сортировке строк, символы которых расположены в случайном порядке.

(20 баллов)

Задание 21. Модифицируйте процедуру MergeSort1 так, чтобы ее действие оставалось прежним, но скройте информацию о том, что она сравнивает символы. Сделайте это, путем замещения всех прямых символьных операций типа:

if Ch1 < Ch2 …

на операторы вызова процедуры:

BEGIN

  Compare(Ch1, Ch2, Result);

  IF Result = ‘<’ …

END

Текст этих процедур будет тривиальным. (Такое изменение программы, чтобы она вела себя по-прежнему, но использовала структуру, легко приспосабливаемую к будущим изменениям, называется профилактическим. См. следующие 2 задания).

(15 баллов)

Задание 22. Измените MergeSort1 таким образом, чтобы она сортировала слова вместо символов. Используйте схему предыдущего упражнения, но теперь напишите процедуры, которые вы бы вставили с соответствующими аргументами типа TEXT в качестве слов.

(20 баллов)

Задание 23. Измените MergeSort1 таким образом, чтобы она сортировала строки вместо символов (см. предыдущее упражнение).

(20 баллов)

10.3 Улучшение MergeSort.

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

Каждый раз после выполнения MergeSort размер каждой серии удваивается. Таблица показывает размеры серий после каждого выполнения процедуры MergeRuns:

Слияние	Размер серии
1	2
2	4
3	8
4	16
5	32
k	2k

Txt считается отсортированным в том случае, когда в нем остается всего одна серия. Для n символов это произойдет, когда выполнены будет k слияний, а 2k>=n. Поскольку при каждом слиянии необходимо прочитать и записать все n символов файла и необходимы k слияний, то количество операций чтения и записи, выполняемых этой программой – n * log2n. Интересно сравнить MergeSort с SelectSort, которая сортирует файл длиной m символов за m*m операций чтения/записи. Чтобы сравнение было честным, предположим, что SelectSort работает с файлом длиной n, а MegreSort1 работает с файлом длиной 2n (процедура MergeSort изначально удваивает размер файла за счет маркеров #. Количество таких маркеров уменьшается по ходу выполнения сортировки, но принятие длины равной 2n – более чем честно по сравнению с SelectSort). Результаты сравнения показаны в таблице:

Длина файла n	Количество операций чтения/записи
SelectSort n2	MergeSort 2n * long22n
10	100	86
100	10 000	1 520
1000	1 000 000	22 000
10000	100 000 000	840 000

MergeSort1 может быть улучшена с использованием преимущества частей файла, который уже отсортированы. С меньшим количеством более длинных серий, потребуется меньше вызовов процедуры MergeRuns/ Конечно, если файл изначально был отсортирован в обратном порядке, все серии будут иметь длину 1 символ, но этот случай будет происходить очень редко. Маркеры серий теперь уже не являются необходимыми, поскольку на границе серий предыдущий считанный символ будет больше, чем следующий.