Мансуров. Основы программирования в среде Lazarus. 2010
.pdfГлава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
var
str, str_lat, str_kyr: string;
i: integer;
{Процедура сортировки методом вставок латиницы}
procedure insert(var str: string);
var
i, j: integer;
v: char;
begin
for i:= 2 to Length(str) do
begin
v:= str[i]; j:= i - 1;
{Условие выхода из цикла: найдено подходящее место для текущего элемента или достигнуто начало строки}
while (str[j] > v) and (j > 0) do
begin
str[j+1]:= str[j];
dec(j);
end;
str[j+1]:= v;
end;
end;
{Процедура сортировки методом вставок кириллицы}
procedure insert_kyr(var str: string);
var
i, j: integer;
v, v1: string[2];
291
4.1 Алгоритмы сортировки
____________________________________________________________________
begin
for i:= 3 to Length(str) do
begin
v:= Copy( str, i, 2);
j:= i - 2;
{Условие выхода из цикла: найдено подходящее место
для текущего элемента или достигнуто начало строки}
while (Copy(str, j, 2) > v) and (j > 0) do begin
v1:= Copy(str, j, 2); str[j+2]:= v1[1]; str[j+3]:= v1[2]; dec(j, 2);
end;
str[j+2]:= v[1]; str[j+3]:= v[2];
end;
end;
begin
str:= 'зжедгвбаhgfedcbaиклмнijklmn'; i:= 1;
str_lat:= ''; str_kyr:= '';
while i <= Length(str) do begin
if ord(str[i]) < 128 then
begin
292
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
str_lat:= str_lat + str[i]; inc(i);
end else begin
str_kyr:= str_kyr + Copy(str, i, 2); inc(i, 2);
end;
end;
writeln(UTF8ToConsole('Исходная строка: '),
UTF8ToConsole(str));
insert(str_lat); // сортировка латиницы insert_kyr(str_kyr); // сортировка кириллицы
str:= Concat(str_lat, str_kyr);
writeln(UTF8ToConsole('Отсортированная строка: '),
UTF8ToConsole(str));
writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Напишем программу сортировки массива строк методом вставок. В про-
грамме строки сортируются по первому символу строки. Например, если задан массив из 4 строк:
Яковлев
Петров
Сидоров
Алексеев
293
4.1 Алгоритмы сортировки
____________________________________________________________________
то программа выдаст массив в следующем виде:
Алексеев
Петров
Сидоров
Яковлев
program insertion_sort_array;
uses
CRT, FileUtil;
var
str: array of string;
i, n: integer;
{Процедура сортировки методом вставок}
procedure insert(var str: array of string); var
i, j: integer; stroka: string;
begin
for i:= 1 to High(str) do begin
stroka:= str[i]; j:= i - 1;
while (str[j][1] > stroka[1]) and (j >= 0) do begin
str[j+1]:= str[j]; dec(j);
end;
str[j+1]:= stroka;
294
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
end;
end;
begin
writeln(UTF8ToConsole('Введите количество строк в массиве')); readln(n);
SetLength(str, n); writeln(UTF8ToConsole('Введите '), n); writeln(UTF8ToConsole('строк(и) символов'));
for i:= 0 to n - 1 do
readln(str[i]);
writeln(UTF8ToConsole('Исходный массив строк'));
for i:= 0 to n - 1 do
writeln(str[i]);
insert(str);
writeln(UTF8ToConsole('Отсортированный массив строк: '));
for i:= 0 to n - 1 do
writeln(str[i]);
writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Отсортируем массив менеджеров (раздел 3.6.3.3. и 4.1.2) методом вставок:
program insertion_sort_file; uses
CRT, SysUtils, OutScr, FileUtil; type
manager= record
295
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