Пусть задана конкретная реализация алгоритма сортировки и значение N. Требуется восстановить некоторые его характеристики. Подобная задача предлагалась на открытой командной олимпиаде по программированию в Санкт-Петербурге в 1996 году.
Ниже приведен алгоритм MSort, который сортирует слиянием заданный массив A из N целых чисел.
Требуется написать программу, которая для заданного N строит пример массива A, на котором достигается максимальное число сравнений. Все элементы массива A должны быть различными и находиться в диапазоне от 1 до N.
procedure MSort (N: integer; var A: list);
var Help: list;
procedure Make (u, v: integer);
var i, j, m, k: integer;
begin
if u < v then
begin
m := (u+v) div 2;
Make (u, m);
Make (m+1, v);
i := u; j := m+1; k := u;
while (i<=m) and (j<=v) do
begin
if A [i] < A [j] then begin Help[k] := A[i]; i := i+1 end
else begin Help[k] := A[j]; j := j+1 end;
k := k+1
end;
while i<=m do begin Help[k] := A[i]; i:=i+1; k:=k+1 end;
while j<=v do begin Help[k] := A[j]; j:=j+1; k:=k+1 end;
for i := u to v do A[i] := Help[i]
end
end
begin {MSort}
Make (1, N)
end;
Приведем рекурсивную процедуру, решающую эту задачу:
procedure Fill (var A: list; u, v: integer; start, step: integer);
begin
if u = v then A [u] := start
else begin
Fill (A, u, (u+v) div 2, start, step*2);
Fill (A, (u+v) div 2 + 1, v, start + step, step*2)
end
end;
Массив А будет заполнен в результате следующего обращения к такой процедуре: Fill(A, 1, N, 1, 1). Кроме того, можно потребовать определить количество сравнений, выполняемых алгоритмом в худшем случае, причем в такой задаче ограничения на величину N уже практически отсутствуют, поэтому решить ее путем подстановки заполненного массива A в исходную процедуру сортировки и включения в нее счетчика сравнений невозможно. Попробуйте написать программу, подсчитывающую количество сравнений, выполняемых приведенной выше процедурой сортировки массива слиянием, по введенному значению N. Саму процедуру сортировки, а также рекурсию, в программе использовать не нужно. Подобные задачи можно поставить и для других алгоритмов сортировки. Постройте пример массива, на котором стандартная процедура QuickSort будет выполнять максимальное количество сравнений. Эта задача имеет и практическое значение. По построенным для различных значений N примерам можно понять для каких именно массивов быстрая сортировка не является эффективной и действительно ли в этом случае количество сравнений имеет порядок O(N2).
Литература
1. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: “Вильямс”, 2000.
2. Вирт Н. Алгоритмы и структуры данных. M.: Мир, 1989.
3. Окулов С.М. Основы программирования. “Информатика”, №23, 2001.
4. Окулов С.M. Сортировка и поиск. “Информатика”, №33, 35, 2000.
5. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
6. Кнут Д. Искусство программирования. Том 3: Поиск и сортировка. М.: “Вильямс”, 2000.
7. Окулов С.М., Шулятников Д.С. Разбор задач международной олимпиады 2000 года. “Информатика”, №12, 2001.
8. Хачиян Л.Г. Проблемы оптимальных алгоритмов в выпуклом программировании, декомпозиции и сортировке. В кн.: Компьютер и задачи выбора. M.: Наука, 1989.
9. Станкевич А.С. Решение задач I Всероссийской командной олимпиады по программированию. “Информатика”, №12, 2001.
|
Главная
Каталог файлов
