Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






BubleSort






 

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

 

Если INPUT уже отсортирован, SelectSort все равно потребует 2N2 выражений 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 может составить N2 (как минимум N). Реально количество проходов для упорядочивания одного символа будет определяться максимальной дистанцией любого символа в INPUT от его окончательного расположения. В случае с фалами со случайно размещенными символами, это число будет составлять значительную долю от N, и общее количество итераций будет также составлять значительную долю от N2.

 

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

 

Заключение

 

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

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

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

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


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.009 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал