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, записывая

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

IF Ch1 <= 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.