| Во всех примерах, относящихся к одномерным массивам, будем использовать следующий тип данных: type list=array[1..N] of <скалярный тип>;
Конкретный тип элемента в большинстве описываемых алгоритмов может быть как любым числовым, так и символьным или даже строковым. Последний тип скалярным не является, но к элементам этого типа применимы все операции сравнения, с помощью которых обычно (но не всегда !!!) и производится сортировка.
Пусть в задаче данные необходимо отсортировать один раз. Тогда выбирать следует тот из известных вам алгоритмов сортировки, на реализацию которого лично у вас уйдет меньше всего времени и отлаживать который тоже не придется. В таком случае ребята обычно реализуют так называемый “пузырьковую” сортировку или сортировку прямым выбором. Конечно, размерность массива при этом должна быть не намного более 1000 элементов, в противном случае время работы программы может оказаться неоправданно большим, так как количество только операций сравнения у обоих упомянутых алгоритмов равно N(N — 1)/2.
Если же размерность массива велика или сортировку требуется проводить на каждом шаге некоторого цикла, то проще всего использовать алгоритм так называемой “быстрой” сортировки [1-4]. Этот алгоритм на практике выполняется за не более Nlog2N операций сравнения и зачастую еще меньшее число операций присваивания, хотя теоретическая оценка для худшего случая является квадратичной по N. В языке программирования C он реализован в виде функции qsort, входящей в библиотеку stdlib. В полной поставке среды программирования Турбо Паскаль данный алгоритм можно найти в файле EXAMPLES\DOS\qsort.pas.
const nn=…{максимальное количество задач};
type rr=record t,k:integer; end; list=array[1..nn] of rr; var time:list; i,n:integer;
procedure QuickSort(var a: List; Lo, Hi: Integer);
procedure Sort(l, r: Integer);
var
i, j, x: integer;
y: rr;
begin
i := l; j := r; x := a[(l+r) DIV 2].t;
repeat
while a[i].t > x do i := i + 1;
while x > a[j].t do j := j - 1;
if i <= j then
begin
y := a[i]; a[i] := a[j]; a[j] := y;
i := i + 1; j := j - 1
end
until i > j;
if l < j then Sort(l, j);
if i < r then Sort(i, r)
end;
begin {QuickSort};
Sort(Lo,Hi)
end;
begin {решение задачи с помощью модифицированной процедуры QuickSort} read(n); for i:=1 to n do
begin
read(time[i].t);
time[i].k:=i
end;
QuickSort(time,1,n);
{сортировали по временам, а печатаем индексы} for i:=1 to n do write(time[i].k:8)
end.
В заключение данного раздела приведем таблицу, в которой для известных универсальных алгоритмов сортировки приведены порядки для количества выполняемых тем или иным алгоритмом в худшем случае операций сравнения и присваивания.
Таким образом наилучшую теоретическую оценку имеют два последних из перечисленных в таблице алгоритмов, однако в практическом программировании для сортировки данных обычно используется QuickSort, как в силу высокой производительности (особенно выигрывает данный алгоритм по числу реально выполняемых присваиваний), так и в силу простой реализации. Тем не менее в олимпиадных задачах данные могут быть представлены так, что отсортировать за отведенное время их можно будет лишь с помощью пирамидальной сортировки. Ее еще называют сортировкой кучей или деревом [1-5]. Особенно полезным при решении некоторых задач, даже напрямую с сортировкой не связанных, может оказаться понимание и умение реализовать операцию “проталкивания” элемента по упорядоченному дереву, с помощью которой и осуществляется данная сортировка. Дополнительную информацию о различных алгоритмах сортировки можно получить в [6].
|
Главная
Каталог файлов
