Мансуров. Основы программирования в среде Lazarus. 2010
.pdfГлава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
Устойчивый алгоритм отсортирует записи в таком виде:
1 A
1С
2B
Рис. 4.6. Результат сортировки устойчивым алгоритмом
а неустойчивый может упорядочить записи в таком виде:
1 С
1A
2B
Рис. 4.7. Результат сортировки неустойчивым алгоритмом
т.е. порядок следования записей с одинаковыми ключами по сравнению с ис-
ходным файлом может нарушиться.
Блок-схему алгоритма составить не представляет труда. Предлагаю это сделать вам самим.
program select_sort; uses
CRT, FileUtil; var
vector: array of integer; i, n: integer;
{ ============= Сортировка выбором ======== } procedure select (var vector: array of integer); var
i, j, count, min, t: integer; begin
281
4.1 Алгоритмы сортировки
____________________________________________________________________
count:= high(vector); for i:= 0 to count - 1 do begin
min:= i;
for j:= i + 1 to count do
if vector[j] < vector[min] then min:= j; t:= vector[min];
vector[min]:= vector[i]; vector[i]:= t;
end;
end;
{ =============================================== }
begin
writeln(UTF8ToConsole('Введите количество элементов массива'));
readln(n);
SetLength(vector, n );
writeln(UTF8ToConsole('Введите '), n);
writeln(UTF8ToConsole('значений массива'));
for i:= 0 to n - 1 do read(vector[i]);
select(vector);
writeln;
writeln(UTF8ToConsole('Отсортированный массив'));
for i:= 0 to n - 1 do write(vector[i], ' ');
writeln;
writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
282
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
Разберем случай сортировки файлов, используя алгоритм выбора. Для это-
го воспользуемся файлом менеджеров созданный в программе раздела 3.6.3.3.
Для того чтобы вам проще было сравнивать результаты, программа создает но-
вый отсортированный файл, а старый не отсортированный оставляет без изме-
нений, хотя в реальных программах, как правило, отсортированный файл заме-
щает собой исходный. Для небольших файлов более эффективным является внутренняя сортировка, т.е. весь файл сначала считывается в некоторый мас-
сив, сортируется и затем записывается на диск на место исходного не отсорти-
рованного файла. Листинг программы сортировки типизированного файла вы-
глядит следующим образом:
program select_sort_file; uses
CRT, FileUtil, SysUtils, OutScr; type
manager= record 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;
{ Сортировка выбором, файла по фамилиям менеджеров }
283
4.1 Алгоритмы сортировки
____________________________________________________________________
procedure select (var vector: array of manager); var
i, j, count, min: integer; t: manager;
begin
count:= high(vector); for i:= 0 to count - 1 do begin
min:= i;
for j:= i + 1 to count do
if vector[j].name < vector[min].name then min:= j; t:= vector[min];
vector[min]:= vector[i]; vector[i]:= t;
end;
end;
{ =============================================== }
begin
{При необходимости укажите полный путь к файлу
или скопируйте файл в папку с данным проектом}
if not FileExists('File_not_sorted.dat') then
begin
writeln(UTF8ToConsole('Файлы не существуют'));
writeln(UTF8ToConsole('Сначала создайте их'));
writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
exit;
284
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
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;
select(vector); // вызов процедуры сортировки методом выбора
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}
285
4.1 Алгоритмы сортировки
____________________________________________________________________
output_to_screen(name_file);
write(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Отсортируем файл менеджеров по количеству проданных компьютеров.
Для этого достаточно в процедуре сортировки select изменить оператор
if vector[j].name[1] < vector[min].name[1] then min:= j;
на
if vector[j].comp < vector[min].comp then min:= j;
4.1.3 Сортировка вставками
Алгоритм этого метода следующий: берем первые два элемента и распола-
гаем их в правильном порядке. Затем берем следующий элемент и вставляем его в нужное место среди тех, что мы уже обработали. Рассматриваемый эле-
мент вставляется в позицию посредством передвижения большего элемента на одну позицию вправо и затем размещением меньшего элемента в освободив-
шуюся позицию. На каждом шаге i элемент a[i] помещается в подходящую по-
зицию среди элементов a[1], ..., a[i-1]. Теперь элементы a[1], ..., a[i] являются упорядоченными, но не "совсем", поскольку среди оставшихся элементов a[i+1], ..., a[n] на каком-нибудь k-м шаге может найтись элемент меньший, чем a[1], ..., a[i], a[i+1], … a[k-1] и он будет вставлен в подходящее место среди этих элементов. Процесс завершится когда последний n-й элемент будет поме-
щен в подходящее для него место. Проиллюстрируем сказанное:
4 |
3 |
2 |
1 |
Рис. 4.8 Исходный массив
286
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
3 4 2 1
Рис. 4.9 Шаг первый, меняются первые два элемента
3 2 4 1
2 3 4 1
Рис. 4.10 Шаг второй, элемент "2" занял свое место, при этом "3" и "4" сдвинулись вправо.
2 3 1 4
2 1 3 4
1 2 3 4
Рис. 4.11 Шаг третий, элемент "1" занял свое место, при этом "2", "3" и "4" сдвинулись вправо.
Алгоритм будет содержать два цикла. Во внешнем цикле указатель i будет двигаться направо ( увеличиваться) начиная с 2, до n, где n количество элемен-
тов. Во внутреннем цикле указатель j сдвигается влево начиная с i-1. На каждом шаге j-м шаге происходит сдвиг элементов вправо до тех пор, пока a[i] не ока-
жется меньше a[j]. Тогда a[i] останется на этом месте и внутренний цикл за-
вершится. Внутренний цикл также может завершиться, когда будет достигнуто начало списка. Рассмотрим программу сортировки строки символов по алфави-
ту методом вставок:
program insertion_sort_string;
uses
CRT, FileUtil;
var
287
4.1 Алгоритмы сортировки
____________________________________________________________________
str: string;
{Процедура сортировки методом вставок}
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;
begin
str:= 'hgfedcba';
writeln(UTF8ToConsole('Исходная строка: '),
UTF8ToConsole(str));
insert(str);
writeln(UTF8ToConsole('Отсортированная строка: '),
UTF8ToConsole(str));
writeln(UTF8ToConsole('Нажмите любую клавишу'));
288
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
readkey;
end.
В этой программе мы рассматривали строку как массив символов. Для строки, состоящей из символов кириллицы, алгоритм необходимо несколько видоизменить. Внешний цикл будет начинаться с 3, так как в кодировке UTF-8
первый байт второго символа строки будет иметь номер 3.
program insertion_sort_string;
uses
CRT, FileUtil;
var
str: string;
{Процедура сортировки методом вставок кириллицы}
procedure insert_kyr(var str: string); var
i, j: integer; v, v1: string[2];
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);
289
4.1 Алгоритмы сортировки
____________________________________________________________________
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:= 'зжедгвба'; writeln(UTF8ToConsole('Исходная строка: '),
UTF8ToConsole(str)); insert_kyr(str);
writeln(UTF8ToConsole('Отсортированная строка: '),
UTF8ToConsole(str));
writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Что будет, если строка "смешанная"? Т.е. содержит и символы кириллицы и символы латиницы. Проще всего поступить следующим образом. Просмот-
реть всю строку и сформировать две новые строки. Одна будет содержать толь-
ко кириллицу, а другая только латиницу. Затем "скормить" процедуре insert_kyr
строку с кириллицей, процедуре insert строку с латиницей. И в завершение объ-
единить отсортированные строки функцией Concat.
program insertion_sort_string;
uses
CRT, FileUtil;
290