BubleSort

SelectSort сортируяфайлыдлины N выполянетпорядка 2N²выражений READ/WRITE. Возможна ли более быстрая сортировка? IFSort и MinSort достаточно эффективны при сортировке строк фиксированной длины, делая работу в один проход и выполняя порядка 2Nвыражений READ/WRITE. Поскольку 2N² всегда больше 2N при всех N> 1, вероятно существуют пути сортировать быстрее чем SelectSort. Новый алгоритм сортировки также нам позволит попрактиковаться в работе с границами файлов с помощь EOF.

Если INPUT уже отсортирован, SelectSort все равно потребует 2N² выражений READ/WRITE. Это наблюдение предлагает нам сделать проверку, не имеем ли мы дело с уже отсортированными данными.

BEGIN {Проверяем F1 на отсортированность}

Sorted:= ‘Y’;

RESET(F1);

IF NOT EOLN(F1)

THEN

BEGIN

READ(F1, Ch1);

WHILE NOT EOLN(F1)

DO

BEGIN

READ(F1, Ch1);

IF Ch2 < Ch1

THEN

Sorted:= ‘N”;

Ch1: Ch2;

END

END

END

Программа перемещает по файлу окно в два символа и если в файле есть фрагмент, который не отсортирован, Sorted будет присвоено ‘N’. Почему бы не использовать этот эффект для сортировки?

F1 копируется в F2, но когда Ch2 <Ch1, эти два символа копируются в F2 в обратном порядке. Таким образом, после некоторого количества проходов по файлу не останется пар символов стоящим в обратном порядке.

Эта идея послужила основой для алгоритма BubleSort, названного так, потому что изменение позиций сортируемых символов напоминает всплывание пузырьков.

DP4

PROGRAM BubbleSort(INPUT,OUTPUT);

{Сортирует первую строку INPUT в OUTPUT}

VAR

Sorted,Ch,Ch1,Ch2:CHAR;

F1,F2:TEXT;

BEGIN {BubbleSort}

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

Sorted:='N';

WHILE Sorted ='N'

DO

BEGIN

{Копируем F1 в F2,проверяя отсортированность

и переставляя первые соседнии символы по порядку}

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

END;

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

END.{BubbleSort}

DP 4.1

BEGIN { Копируем F1 в F2,проверяя отсортированность

и переставляя первые соседнии символы по порядку}

Sorted:='Y';

RESET(F1);

REWRITE(F2);

IF NOT EOF(F1)

THEN

BEGIN

READ(F1,Ch1);

WHILE NOT EOLN(F1)

DO { По крайней мере два символа остается для Ch1,Ch2 }

BEGIN

READ(F1,Ch2);

{ Выводим min(Ch1,Ch2) в F2, записывая

отсортированные символы }

END;

WRITELN(F2,Ch1) { Выводим последний символ в F2 }

END

END

DP 4.1.1

{ Выводим min(Ch1,Ch2) в F2, записывая

отсортированные символы }

IFCh1 <= Ch2

THEN

BEGIN

WRITE(F2,Ch1);

Ch1:=Ch2

END

ELSE

BEGIN

WRITE(F2,Ch2);

Sorted:= 'N'

END

DP4.2

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

REWRITE(F1);

WHILE NOT EOLN

DO

BEGIN

READ(Ch);

WRITE(F1,Ch);

END;

WRITELN(F1)

END;

Разделы

DP4.4 { Копируем F2 в F1 } и DP4.3{ Копируем F1 в OUTPUT }

выполняются аналогично DP 4.2

Проанализируем трудоемкость алгоритма. Допустим для файла длины N минимальный элемент данных находится в позиции m.

В процессе сортировки этот элемент перемещается на первую позицию в файле за m итераций. В случае если он расположен на последней позиции, потребуется N итераций. Аналогично с остальными элементами. Таким образом, максимальное количество итераций для BubbleSort может составить N² (как минимум N). Реально количество проходов для упорядочивания одного символа будет определяться максимальной дистанцией любого символа в INPUT от его окончательного расположения. В случае с фалами со случайно размещенными символами, это число будет составлять значительную долю от N, и общее количество итераций будет также составлять значительную долю от N².

Является ли BubbleSort более быстрым алгоритмом сортировки, чем SelectSort? При работе с последовательностями близкими к отсортированным – да. В случае с фалами со случайно размещенными символами, BubbleSort не будет иметь значительных преимуществ перед SelectSort.

Заключение

Переменные CFPascal могут принимать значения, которые представлены одним символом или последовательностью символов (файл) в зависимости от того, объявлены они как CHAR или TEXT. Переменные типа TEXT позволяют организовать хранение данных практически неограниченного размера. Но для работы с файловыми переменными требуется жесткая дисциплина. Они должны быть подготовлены к записи с помощью выражения REWRITE и закрыты с помощью выражения WRITELN, подготовлены для чтения с помощью выражения RESET. Символы считываются из файла точно в том порядке, в каком они были записаны.

SelectSort – программа сортировки общего назначения, которая может сортировать файлы неограниченного размера. Но программы из семейства MinSortc ограниченной функциональностью рассмотренные в части 3 работают быстрее. Программа BubbleSort, но ее скорость нестабильна и зависит от сортируемых данных. В некоторых случаях она работает эффективнее, чем SelectSort, в других – примерно также.

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

Текстовые файлы могут быть организованы в строки, границы строк могут быть обработаны с помощью выражений EOLN – определение границы строки; READLN – для перемещения курсора за маркер конца строки, WRITELN – для записи маркера конца строки. Конец данных в файле может быть определен с помощью оператора EOF. Схема процедуры чтения или копирования файла значительно проще, когда используются естественные маркеры конца файла и функции EOLN и EOF, чем искусственно введенный символ конца последовательности #.