2015-04-06
380
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:
| Слияние | Размер серии |
| 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 000 | 1 520 | |
| 1 000 000 | 22 000 | |
| 100 000 000 | 840 000 |
MergeSort1 может быть улучшена с использованием преимущества частей файла, который уже отсортированы. С меньшим количеством более длинных серий, потребуется меньше вызовов процедуры MergeRuns/ Конечно, если файл изначально был отсортирован в обратном порядке, все серии будут иметь длину 1 символ, но этот случай будет происходить очень редко. Маркеры серий теперь уже не являются необходимыми, поскольку на границе серий предыдущий считанный символ будет больше, чем следующий.
Пример улучшенной сортировки показан ниже. Точки показаны лишь для пометки границы серий, и в действительности не существуют.
| Шаг | Разделенные строки | Склеенные строки | |
| wrcaot | |||
| Разделение | w·c | r·aot | |
| Слияние | rw·acot | ||
| Разделение | rw | acot | |
| Слияние | acortw |
Первое разделение сохранило серию aot, потому что эти символы уже находятся в порядке возрастания. В результате понадобилось только две операции слияния вместо трех.
Довольно трудно проанализировать эффект от использования естественных серий в склеенных файлов, потому что прирост зависит от того, как отклоняются серии от худшего случая – от файла отсортированного в обратном порядке. Однако, даже в худшем случае количество операций чтения/записи уменьшится с 2n*log22n до n*log2n, что примерно в 6 раз лучше при n = 1000. Проект улучшенной процедуры MergeSort2, использующей существующие серии практически тот же самый, что и для MergeSort1, за исключением того, что не нужно больше вставлять маркеры #:
