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

Идея данного метода состоит в том, что каждый раз, имея уже упорядоченный массив из 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. Охарактеризуйте сортировку включением.

20. Файлы

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

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

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

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

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

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

'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 f1 : file of real;f2 : file of integer;fLi : file of M;

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

var f: file;

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

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

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

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

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

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

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

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

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

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