Сортировка обменом (методом «пузырька»)

Идея метода заключается в том, что последовательно сравниваются пары соседних элементов массива. Если они располагаются не в том порядке, то совершаем перестановку, меняя местами пару соседних элементов. После одного такого прохода на последнем месте номер N окажется максимальный элемент («всплыл» первый «пузырек»). Следующий проход должен рассматривать элементы до предпоследнего и так далее. Всего требуется n –1 проход. Вычислительная сложность сортировки обменом o(n * n).

Пример 19.3:Сортировка обменом по возрастанию массива a из n целых чисел. (Базовый вариант)

program Sort_Obmen1;

var a: array [1..100] of integer;

n, i, k, x: integer;

Begin

write ('количество элементов массива ');

read (n);

for i:=1 to n do read (a [i]);

for k:= n –1 downto 1 do { k – количество сравниваемых пар }

for i:=1 to k do

if a [ i ]> a [ i +1] then

{меняем местами соседние элементы}

begin x:= a [ i ]; a [ i ]:= a [ i +1]; a [ i +1]:= x; end;

for i:=1 to n do write (a [ i ],' '); {упорядоченный массив}

end.

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

Пример 19.4: Сортировка обменом с проверкой факта перестановки.

program sort_obmen2;

var a: array [1..100] of integer;

n, i, k, x: integer; p: boolean;

Begin

write ('количество элементов массива ');

read (n);

for i:=1 to n do read (a [ i ]);

k:= n –1; {количество пар при первом проходе}

p:=true; {логическая переменная p истинна, если были

перестановки, т.е. нужно продолжать сортировку}

while p do

Begin

p:=false;

{Начало нового прохода. Пока перестановок не было.}

for i:=1 to k do

if a [ i ]> a [ i +1] then

Begin

x:= a [ i ]; a [ i ]:= a [ i +1]; a [ i +1]:= x;

{меняем элементы местами}

p:=true; {и запоминаем факт перестановки}

end;

k:= k –1;

{уменьшаем количество пар для следующего прохода}

end;

for i:=1 to n do write (a [ i ],' '); {упорядоченный массив}

end.

Следующая модификация алгоритма сортировки обменом получается при запоминании места последней перестановки. Если при очередном проходе последней парой элементов, которые поменялись местами, были a [ i ] и a [ i +1], то элементы массива с i +1 до последнего уже стоят на своих местах. Использование этой информации позволяет нам сделать количество пар для следующего прохода равным i –1.

Пример 19.5: Сортировка обменом с запоминанием места последней перестановки.

program sort_obmen3;

var a: array [1..100] of integer;

n, i, k, x, m: integer;

Begin

write ('количество элементов массива ');

read (n);

for i:=1 to n do read (a [ i ]);

k:= n –1; {количество пар при первом проходе}

while k >0 do

Begin

m:=0;

{пока перестановок на этом проходе нет, место равно 0}

for i:=1 to k do

if a [ i ]> a [ i +1] then

Begin

x:= a [ i ]; a [ i ]:= a [ i +1]; a [ i +1]:= x; {меняем элементы местами}

m:= i; {и запоминаем место перестановки}

end;

k:= m –1; {количество пар зависит от места последней перестановки}

end;

for i:=1 to n do write (a [ i ],' '); {упорядоченный массив}

end.

Сортировка включением

Идея данного метода состоит в том, что каждый раз, имея уже упорядоченный массив из k элементов, мы добавляем еще один элемент, включая его в массив таким образом, чтобы упорядоченность не нарушилась. Сортировка может производиться одновременно с вводом массива.

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

При использовании линейного поиска вычислительная сложность сортировки включением составляет o(n * n), а при использовании двоичного поиска – o(n * log ₂ n).

Пример 19.6:Сортировка по возрастанию массива a из n целых чисел включением с линейным поиском.

program sort_include1;

var a: array [1..100] of integer;

n, i, k, x: integer;

Begin

write ('количество элементов массива ');

read (n);

read (a [1]); { for i:=1 to n do read (a [ i ]);}

{ k – количество элементов в упорядоченной части массива}

for k:=1 to n –1 do

Begin

read (x); { x:= a [ k +1];}

i:= k;

while (i >0) and (a [ i ]> x) do

Begin

a [ i +1]:= a [ i ];

i:= i –1;

end;

a [ i +1]:= x;

end;

for i:=1 to n do write (a [ i ],' '); {упорядоченный массив}

end.

Пример 19.7: Сортировка по возрастанию массива a из n целых чисел включением с двоичным поиском.

program sort_include2;

var a: array [1..100] of integer;

n, i, k, x, c, left, right: integer;

Begin

write ('количество элементов массива '); read (n);

read (a [1]); { for i:=1 to n do read (a [ i ]);}

{ k – количество элементов в упорядоченной части массива}

for k:=1 to n –1 do

Begin

read (x); { x:= a [ k +1];}

left:=1; right:= k;

{левая и правая граница фрагмента для поиска}

while left < right do

{двоичный поиск последнего вхождения}

Begin

c:=(left + right + 1) div 2;

{середина с округлением в большую сторону}

if x >= a [ c ] then left:= c

{берем правую половину с серединой}

else right:= c – 1; {берем левую половину без середины}

end;

if x >= a [ left ] then left:= left + 1;

{сдвигаем на 1 вправо часть массива, освобождая место

для включения x}

for i:= k downto left do a [ i +1]:= a [ i ];

a [ left ]:= x;

end;

for i:=1 to n do write (a [ i ],' '); {упорядоченный массив}

end.

Контрольные вопросы

1. Сформулируйте назначение алгоритмов сортировок.

2. Перечислите виды алгоритмов сортировок.

3. Охарактеризуйте сортировку выбором.

4. Охарактеризуйте сортировку обменом.

5. Охарактеризуйте сортировку включением.

Файлы

Введение файлового типа в язык Паскаль вызвано необходимостью обеспечить возможность работы с периферийными (внешними) устройствами ЭВМ, предназначенными для ввода, вывода и хранения данных.

Файловый тип данных или файл определяет упорядоченную совокупность произвольного числа однотипных компонент.

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

Понятие файла достаточно широко. Это может быть обычный файл на диске, коммуникационный порт ЭВМ, устройство печати, клавиатура или другие устройства.

При работе с файлами выполняются операции ввода – вывода. Операция ввода означает перепись данных с внешнего устройства (из входного файла) в основную память ЭВМ, операция вывода – это пересылка данных из основной памяти на внешнее устройство (в выходной файл).

Файлы на внешних устройствах часто называют физическими файлами. Их имена определяются операционной системой. В программах на языке Паскаль имена файлов задаются с помощью строк. Например, имя файла на диске может иметь вид:

'A:lab1.dat'

'c:\abc150\pr.pas'

'lab3.pas'.

Операционная система MS DOS не делает особого различия между файлами на дисках и лентах и устройствами ЭВМ и портами коммуникаций. В Турбо Паскале могут использоваться имена устройств и портов, определенные в MS DOS, например:

'CON', 'LPT1', 'PRN', 'COM1', 'AUX', 'NUL'.

С файловой системой связано понятие буфера ввода–вывода. Ввод и вывод данных осуществляется через буфер. Буфер – это область в памяти, которая выделяется для каждого файла. При записи в файл вся информация сначала направляется в буфер и там накапливается до тех пор, пока весь объем буфера не будет заполнен. Только после этого или после специальной команды сброса происходит передача данных на внешнее устройство. При чтении из файла данные вначале считываются в буфер, причем данных считывается не столько, сколько запрашивается, а сколько поместится в буфер.

Механизм буферизации позволяет более быстро и эффективно обмениваться информацией с внешними устройствами.

Для работы с файлами в программе необходимо определить файловую переменную. Турбо Паскаль поддерживает три файловых типа: текстовые файлы, компонентные файлы, бестиповые файлы.

Описание файловых переменных текстового типа производится с помощью служебного слова text, например:

var tStory: text;

Описание компонентных файлов имеет вид:

var fComp: file of t;

где t – тип компоненты файла. Примеры описания файловой переменной компонентного типа:

type m = array [1..500] of longint;

var f 1: file of real;

f 2: file of integer;

fLi: file of M;

Бестиповые файлы описываются с помощью служебного слова file:

var f: file;

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

Турбо Паскаль вводит ряд процедур и функций, применимых для любых типов файлов: assign, reset, rewrite, close, rename, erase, eof, ioresult.

Процедура assign (var f; FileName: String) связывает логический файл f с физическим файлом, полное имя которого задано в строке FileName.

Процедура reset (var f) открывает логический файл f для последующего чтения данных или, как говорят, открывает входной файл. После успешного выполнения процедуры Reset файл готов к чтению из него первого элемента.

Процедура rewrite (var f) открывает логический файл f для последующей записи данных (открывает выходной файл). После успешного выполнения этой процедуры файл готов к записи в него первого элемента.

Процедура close (var f) закрывает открытый до этого логический файл. Вызов процедуры close необходим при завершении работы с файлом. Если по какой–то причине процедура Close не будет выполнена, файл все же будет создан на внешнем устройстве, но содержимое последнего буфера в него не будет перенесено. Для входных файлов использование оператора закрытия файла необязательно.

Логическая функция eof (var f): Boolean возвращает значение true, когда при чтении достигнет конца файла. Это означает, что уже прочитан последний элемент в файле или файл после открытия оказался пуст.

Процедура rename (var f; NewName: string) позволяет переименовать физический файл на диске, связанный с логическим файлом f. Переименование возможно после закрытия файла.

Процедура erase (var f) уничтожает физический файл на диске, который был связан с файловой переменной f. Файл к моменту вызова процедуры erase должен быть закрыт.

Функция ioresult:integer возвращает целое число, соответствующее коду последней ошибки ввода–вывода. При нормальном завершении операции функция вернет значение 0. Значение функции ioresult необходимо присваивать какой–либо переменной, так как при каждом вызове функция обнуляет свое значение. Функция ioresult работает только при выключенном режиме проверок ошибок ввода–вывода или с ключом компиляции {$I–}.

Текстовые файлы

Особое место в языке Паскаль занимают текстовые файлы, компоненты которых имеют символьный тип. Для описания текстовых файлов в языке определен стандартный тип text:

var tf 1, tf 2: text;

Текстовые файлы представляют собой последовательность строк, а строки – последовательность символов. Строки имеют переменную длину, каждая строка завершается признаком конца строки.

С признаком конца строки связана функция eoln (var t: text):boolean, где t – имя текстового файла. Эта функция принимает значение true, если достигнут конец строки, и значение false, если конец строки не достигнут.

Для операций над текстовыми файлами, кроме перечисленных, определены также операторы обращения к процедурам:

readln (t) – пропускает строку до начала следующей;

writeln (t) – завершает строку файла, в которую производится запись, признаком конца строки и переходит к началу следующей.

Для работы с текстовыми файлами введена расширенная форма операторов ввода и вывода. Оператор

read (t, x 1, x 2,... xk)

эквивалентен группе операторов

Begin

read (t, x 1);

read (t, x 2);

read (t, xk)

end;

Здесь t – текстовый файл, а переменные x 1, x 2,... xk могут быть либо переменными целого, действительного или символьного типа, либо строкой. При чтении значений переменных из файла они преобразуются из текстового представления в машинное.

Оператор

write (t, x 1, x 2,... xk);

эквивалентен группе операторов

Begin

write (t, x 1);

write (t, x 2);

write (t, xk)

end;

Здесь t – также текстовый файл, но переменные x 1, x 2,..., xk могут быть целого, действительного, символьного, логического типа или строкой. При записи значений переменных в файл они преобразуются из внутреннего представления в текстовый.

К текстовым файлам относятся стандартные файлы INPUT, OUTPUT.

Рассмотренные ранее операторы ввода – вывода являются частным случаем операторов обмена с текстовыми файлами, когда используются стандартные файлы ввода–вывода INPUT, OUTPUT.

Работа с этими файлами имеет особенности:

- имена этих файлов в списках ввода–вывода не указываются;

- применение процедур reset, rewrite и close к стандартным файлам ввода–вывода запрещено;

- для работы с файлами INPUT, OUTPUT введена разновидность функции eoln без параметров;

- Турбо Паскаль вводит дополнительные процедуры и функции, применимые только к текстовым файлам, это SetTextBuf, Append, Flush, SeekEOLn, SeekEOF.

Процедура SetTextBuf (var f: text; var Buf; BufSize: word) служит для увеличения или уменьшения буфера ввода–вывода текстового файла f. Значение размера буфера для текстовых файлов по умолчанию равно 128 байтам. Увеличение размера буфера сокращает количество обращений к диску. Рекомендуется изменять размер буфера до открытия файла. Буфер файла начнется с первого байта переменной Buf. Размер буфера задается в необязательном параметре BufSiz e, а если этот параметр отсутствует, размер буфера определяется длиной переменной Buf.

Процедура append (var f: text) служит для специального открытия выходных файлов. Она применима к уже существующим физическим файлам и открывает их для дозаписи в конец файла.

Процедура flush (var f: text) применяется к открытым выходным файлам. Она принудительно записывает данные из буфера в файл независимо от степени его заполнения.

Функция SeekEOLn (var f: text): boolean возвращает значение true, если до конца строки остались только пробелы.

Функция SeekEOF (var f: text): boolean возвращает значение true, если до конца файла остались строки, заполненные пробелами.

Компонентные файлы

Компонентный или типизированный файл – это файл с объявленным типом его компонент. Компонентные файлы состоят из машинных представлений значений переменных, они хранят данные в том же виде, что и память ЭВМ.

Описание величин файлового типа имеет вид:

type m = file of T;

где m – имя файлового типа; Т – тип компоненты. Например:

Type

fio = string[20];

spisok = file of fio;

Var

stud, prep: spisok;

Здесь stud, prep – имена файлов, компонентами которых являются строки.

Описание файлов можно задавать в разделе описания переменных:

Var

fsimv: file of char;

fr: file of real;

Компонентами файла могут быть все скалярные типы, а из структурированных – массивы, множества, записи. Практически во всех конкретных реализациях языка Паскаль конструкция «файл файлов» недопустима.

Все операции над компонентными файлами производятся с помощью стандартных процедур: reset, rewrite, read, write, close.

Для ввода–вывода используются процедуры:

read (f, x);

write (f, x);

где f – имя логического файла; x – либо переменная, либо массив, либо строка, либо множество, либо запись с таким же описанием, какое имеет компонента файла.

Выполнение процедуры read (f, x) состоит в чтении с внешнего устройства одной компоненты файла и запись ее в x. Повторное применение процедуры read (f, x) обеспечит чтение следующей компоненты файла и запись ее в x.

Выполнение процедуры write (f, x) состоит в записи x на внешнее устройство как одной компоненты. Повторное применение этой процедуры обеспечит запись x как следующей компоненты файла.

Для работы с компонентными файлами введена расширенная форма операторов ввода и вывода:

read (f, x 1, x 2,... xk)

write (f, x 1, x 2,... xk)

Здесь f – компонентный файл, а переменные x 1, x 2,..., xk должны иметь тот же тип, что и объявленный тип компонент файла f.

Бестиповые файлы

Бестиповые файлы позволяют записывать на диск произвольные участки памяти ЭВМ и считывать их с диска в память. Операции обмена с бестиповыми файлами осуществляются с помощью процедур BlokRead и BlockWrite. Кроме того, вводится расширенная форма процедур reset и rewrite. В остальном принципы работы остаются такими же, как и с компонентными файлами.

Перед использованием логический файл

var f: file;

должен быть связан с физическим с помощью процедуры assign. Далее файл должен быть открыт для чтения или для записи процедурой reset или rewrite, а после окончания работы закрыт процедурой close.

При открытии файла длина буфера устанавливается по умолчанию в 128 байт. Турбо Паскаль позволяет изменить размер буфера ввода–вывода, для чего следует открывать файл расширенной записью процедур

reset (var f: file; BufSize: word);

или

rewrite (var f: file; BufSize: word);

Параметр BufSize задает число байтов, считываемых из файла или записываемых в него за одно обращение. Минимальное значение BufSize – 1 байт, максимальное – 64 Кбайта.

Чтение данных из бестипового файла осуществляется процедурой

BlockRead (var f: file; var x; count: word;

var QuantBlock: word);

Эта процедура осуществляет за одно обращение чтение в переменную X количества блоков, заданное параметром count, при этом длина блока равна длине буфера. Значение count не может быть меньше 1. За одно обращение нельзя прочесть больше, чем 64 Кбайтов.

Необязательный параметр QuantBlock возвращает число блоков (буферов), прочитанных текущей операцией BlockRead. В случае успешного завершения операции чтения QuantBlock = count, в случае аварийной ситуации параметр QuantBlock будет содержать число удачно прочитанных блоков. Отсюда следует, что с помощью параметра QuantBlock можно контролировать правильность выполнения операции чтения.

Запись данных в бестиповой файл выполняется процедурой

BlockWrite (var f: file; var x; count: word;

var QuantBlock: word);

которая осуществляет за одно обращение запись из переменной x количества блоков, заданное параметром count, при этом длина блока равна длине буфера.

Необязательный параметр QuantBlock возвращает число блоков (буферов), записанных успешно текущей операцией BlockWrite.