Глава 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