4.1 Алгоритмы сортировки
____________________________________________________________________
лизовывать по разному. Вот пример другой реализации того же алгоритма.
program quick_sort;
uses
CRT, FileUtil;
type
vector= array of integer;
var
i, n: integer;
sorted_array: vector; // сортируемый массив
{ ============ Метод быстpой сортировки ======= }
procedure QuickSort(var sorted_array: vector); { rec_sort - рекурсивная процедура }
procedure rec_sort(first, last: integer;
var sorted_array: vector);
{ first, last - первый и последний элементы текущей группы }
var
i: integer; // указатель для левого списка
j: integer; // указатель для правого списка
middle: integer; // средний элемент списка temp: integer;
begin
i:= first; // первый элемент текущего списка j:= last; // последний элемент текущего списка
middle:= sorted_array[(first + last) div 2]; repeat
while sorted_array[i] < middle do
306
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
i:= i + 1;
while middle < sorted_array[j] do j:= j - 1;
if i <= j then begin
temp:= sorted_array[i]; sorted_array[i]:= sorted_array[j]; sorted_array[j]:= temp;
i:= i + 1; j:= j - 1;
end; until i > j;
{рекурсивные вызовы процедуры для левых и правых подсписков} if first < j then rec_sort(first, j, sorted_array); if i < last then rec_sort(i, last, sorted_array);
end;
{ ==================================================== }
begin
{первый вызов рекурсивной процедуры} rec_sort(0, n - 1, sorted_array);
end;
{=======================================}
begin
writeln(UTF8ToConsole('Введите количество элементов массива')); readln(n);
SetLength(sorted_array, n); writeln(UTF8ToConsole('Введите элементы массива'));
307
4.1 Алгоритмы сортировки
____________________________________________________________________
for i:= 0 to n - 1 do read(sorted_array[i]);
QuickSort(sorted_array); writeln(UTF8ToConsole('Отсортированный массив:')); writeln;
for i:= 0 to n - 1 do write(sorted_array[i], ' ');
writeln;
writeln;
writeln(UTF8ToConsole('Нажмите любую клавишу')); readkey;
end.
Напишем программу сортировка файла алгоритмом Хоара.
program quick_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;
308
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
name_file: string;
{ ========= Метод быстpой сортировки ======== }
procedure QuickSort(var sorted_array: array of manager);
{ rec_sort - рекурсивная процедура } procedure rec_sort(first, last: integer;
var sorted_array: array of manager);
{ first, last - первый и последний элементы текущей группы } var
i: integer; // указатель для левого списка j: integer; // указатель для правого списка middle: manager; // средний элемент списка temp: manager;
begin
while (first < last) do begin
middle:= sorted_array[(first + last) div 2]; i:= Pred(first);
j:= Succ(last); while true do begin
repeat dec(j);
until sorted_array[j].name <= middle.name; repeat inc(i);
until sorted_array[i].name >= middle.name; if i >= j then break;
temp:= sorted_array[i];
309
4.1 Алгоритмы сортировки
____________________________________________________________________
sorted_array[i]:= sorted_array[j];
sorted_array[j]:= temp;
end;
{рекурсивный вызов процедуры}
if first < j then rec_sort(first, j, sorted_array); first:= Succ(j);
end;
end;
{ ======================================= } begin
{первый вызов рекурсивной процедуры}
rec_sort(0, n - 1, sorted_array);
end;
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);
310