Мансуров. Основы программирования в среде Lazarus. 2010

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

4.1.4 Метод быстрой сортировки

Алгоритм быстрой сортировки был разработан К. Хоаром в 1960 году.

Быструю сортировку называют еще сортировкой с разделением или просто ал-

горитмом сортировки Хоара. Суть метода заключается в следующем: выбира-

ется какой-нибудь элемент списка, называемый базовым или опорным. После этого сортируемый список делится на две части: в левую помещаются все эле-

менты меньшие базового элемента, в правую элементы, большие базового эле-

мента, а сам базовый элемент при этом окажется на нужном месте в списке. Да-

лее полученные два списка сортируются таким же образом, т.е. вновь выбира-

ются базовые элементы (уже внутри подсписков), подсписки делятся на два, в

левую помещаются элементы меньшие базового элемента, в правую элементы,

большие базового элемента и т.д. При реализации алгоритма процедура, вы-

полняющая основные действия по сортировке вызывает саму себя. Такой вызов функции или процедуры самой себя называется рекурсией. Рассмотрим алго-

ритм подробнее.

Сначала поговорим о выборе базового элемента. Идеальным случаем было бы выбор в качестве базового элемента среднего по значению элемента списка.

Но для этого нужно предварительно просмотреть весь список, вычислить сред-

нее значение, затем снова просмотреть весь список – имеется ли это среднее значение среди элементов списка и все это рекурсивно! По количеству опера-

ций это равносильно самой сортировке.

Если в качестве базового выбирать минимальный или максимальный эле-

мент списка, то, во-первых, для этого все равно нужен предварительный про-

смотр всего списка (подсписков в дальнейшем), во-вторых, что еще хуже, при разделении списка на два, один из подсписков окажется пустым, поскольку все элементы списка будут находиться по одну сторону от базового. При числе элементов списка n, будут выполнены n рекурсивных вызовов. При большом числе n может не хватить стековой памяти, к тому же алгоритм может просто

301

4.1 Алгоритмы сортировки

____________________________________________________________________

зациклиться.

Не вдаваясь в дальнейшие тонкости, скажем, что чаще всего в качестве ба-

зового элемента берут элемент средний по месту нахождения элемента в спи-

ске. Итак, алгоритм:

Заводятся два указателя (индекса) i и j. В начале i 1 и j n , где n -

число сортируемых записей.

На каждом шаге выполняется разбиение записей на две подгруппы так,

ваемой группы из n записей (элементов). Имеются два внутренних цикла. Пер-

второй внутренний цикл выполняет просмотр элементов левой подгруппы слева. Сравниваются Rbase с Ri , i 1,2, до тех пор, пока не встретится Ri > Rbase .

Теперь возможны два случая:

1. i < j, это означает, что два элемента, на которые указывают индексы расположены в неправильном порядке. Действительно, элемент, который нахо-

дится в левом подсписке больше, чем базовый элемент, а элемент, который на-

ходится в правом подсписке, меньше базового элемента.

Меняем местами элементы и продолжаем выполнение внутренних циклов.

2. i >= j, это означает, что текущая подгруппа успешно разделена. Выпол-

нение внутренних циклов завершается.

Внешний цикл начинает свою работу вновь с определения базового эле-

мента, теперь уже для текущей подгруппы.

302

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Теоретические расчеты эффективности метода показывают в среднем n log2 (n) операций сравнений.

Напишем программу быстрой сортировки для массива с произвольным числом элементов. В качестве элементов возьмем целые числа.

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

while (first < last) do begin

303

4.1 Алгоритмы сортировки

____________________________________________________________________

middle:= sorted_array[(first + last) div 2]; i:= pred(first);

j:= succ(last); while true do begin

repeat dec(j);

until sorted_array[j] <= middle; repeat inc(i);

until sorted_array[i] >= middle; if i >= j then break;

temp:= sorted_array[i]; 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;

{ ======= конец процедуры rec_sort ======== } begin

{ первый вызов рекурсивной процедуры} rec_sort(0, n - 1, sorted_array);

end;

{ ======= конец процедуры QuickSort ======== }

304

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