4.1 Алгоритмы сортировки
____________________________________________________________________
name: string[18]; comp: integer; end;
var
company: manager;
f_not_sorted, f_sorted: File of manager; vector: array of manager;
i, n: integer; name_file: string;
{Процедура сортировки методом вставок файла по фамилиям менеджеров} procedure insert(var vector: array of manager);
var
i, j, count: integer; t: manager;
begin
count:= high(vector); for i:= 0 to count do begin
t:= vector[i]; j:= i - 1;
while (vector[j].name > t.name) and (j >= 0) do begin
vector[j + 1] := vector[j]; dec(j);
end;
vector[j + 1] := t; end;
end;
296
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
{ ================================================ }
begin
{При необходимости укажите полный путь к файлу
или скопируйте файл в папку с данным проектом}
if not FileExists('File_not_sorted.dat') then
begin
writeln(UTF8ToConsole('Файлы не существуют'));
writeln(UTF8ToConsole('Сначала создайте их'));
writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
exit;
end;
AssignFile(f_not_sorted,'File_not_sorted.dat');
Reset(f_not_sorted);
// Определение количества записей в файле
n:= System.FileSize(f_not_sorted);
SetLength(vector, n);
{Подготовка к внутренней сортировке,
считывание записей файла в массив,
в процедуру передается массив, а не файл.}
i:= 0;
while not Eof(f_not_sorted) do begin
Read(f_not_sorted, company); vector[i]:= company; // сортируемый массив i:= i + 1;
end;
insert(vector); // вызов процедуры сортировки методом вставок
297
4.1 Алгоритмы сортировки
____________________________________________________________________
CloseFile(f_not_sorted);
AssignFile(f_sorted, 'File_sorted.dat');
Rewrite(f_sorted);
for i:= 0 to n - 1 do Write(f_sorted, vector[i]); CloseFile(f_sorted); name_file:= 'File_sorted.dat';
{Вызов процедуры для вывода на экран сводной ведомости.
Процедура находится в модуле OutScr}
output_to_screen(name_file);
write(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Во внутреннем цикле метода вставок осуществляется две проверки. Одна для нахождения подходящего места текущему элементу, а другая (j>0, если нумерация индексов начинается с 1 и j>=0, если нумерация индексов начина-
ется с 0) для предотвращения выхода за пределы левого края массива (строку символов можно рассматривать как массив, элементами которого являются от-
дельные символы строки).
Однако эта дополнительная проверка, как показывают многочисленные эксперименты, замедляют работу алгоритма почти до 7%. Выходом из этой си-
туации является помещение в первый элемент массива так называемого "сто-
рожевого" элемента, который являлся бы минимальным элементом массива. Но заранее (до начала работы алгоритма) значение минимального элемента, как правило, неизвестно. Следовательно, необходимо предварительно просмотреть весь массив, найти минимальный элемент и переместить его в начало массива
(фактически это выполнение первого цикла сортировки методом выбора). Те-
перь, когда первый элемент уже находится в требуемой позиции, можно запус-
298
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
кать алгоритм сортировки методом вставок без проверки на выход за пределы начала массива. Программа для улучшенного метода вставок выглядит сле-
дующим образом:
program modify_insertion_sort_string;
uses
CRT, FileUtil;
var
str: string;
{Процедура, реализующая улучшенный алгоритм
сортировки методом вставок}
procedure insert(var str:string);
var
i, j: integer;
v: char;
min: integer;
begin
{Поиск минимального элемента в строке}
min:= 1;
for i:= 2 to length(str) do
if str[i] < str[min] then min:= i;
{Меняем местами найденный символ с первым
символом в строке}
v:= str[1];
str[1]:= str[min];
str[min]:= v;
{Реализация собственно метода вставок}
for i:= 2 to length(str) do
299
4.1 Алгоритмы сортировки
____________________________________________________________________
begin
v:= str[i]; j:= i - 1;
// теперь в цикле проверяется только одно условие
while str[j] > v do
begin
str[j+1]:= str[j];
dec(j);
end;
str[j+1]:= v;
end;
end;
begin
str:= 'dkfhytcba';
writeln(UTF8ToConsole('Исходная строка: '),
UTF8ToConsole(str));
insert(str);
writeln(UTF8ToConsole('Отсортированная строка: '),
UTF8ToConsole(str));
writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
В качестве упражнения напишите программы сортировки строки с кирил-
лицей, массива строк и файла менеджеров улучшенным методом вставок.
Как и предыдущие алгоритмы, сортировка методом вставок принадлежит классу O(n2). Если же список частично отсортирован, алгоритм метода вставок работает очень быстро и имеет порядок O(n). Немаловажно и то, что алгоритм является устойчивым.
300