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