Презентация, доклад решения олимпиадных задач по программированию. Олимпиадная Задача ‘’Анти-быстрая сортировка.

знают что он не так быстр на больших числах…

:= left;
j := right;
repeat
while a[i] < key do {первый while}
inc(i);
while key < a[j] do {второй while}
dec(j);
if i <= j then begin
buf := a[i];
a[i] := a[j];
a[j] := buf;
inc(i);
dec(j);
end;
until i > j;

которых она работает очень долго. Оценивать время работы алгоритма будем количеством сравнений с элементами массива (то есть суммарным количеством сравнений в первом и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.

1 <= N <= 70 000, время 1 с. Вывод в файл antiqs.out. Вывести перестановку чисел от 1 до N, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них. Примеры
Ввод
3
Вывод
1 3 2

отрезок делится на две, почти, равные части. Если бы отрезок делился ровно пополам, то длина сортируемых отрезков на каждом шаге уменьшалась бы в 2 раза. Таким образом, случай тривиального отрезка – из одного элемента- достигался быза log2 N делений.

длину 1. Если при каждом делении отрезка одна из частей будет иметь длину 1, то количество делений для сортировки массива вместо log2 N будет порядка N.

копировать содержимое массива b в массив a, потом сортировать. Теперь о том, как подсчитывается количество сравнений. Нужно объявить переменную целого типа, обнулять ее каждый раз, когда массив b копируется в a, и увеличивать на единицу при каждом выполнении цикла while и при каждом выходе из цикла while:

inc(i);
end;
inc(count);
Счётчик внутри цикла учитывает, сколько раз условие цикла стало истинным, счётчик после цикла учитывает, сколько раз условие стало ложным, вследствие чего цикл завершился. В сумме как раз и получается количество сравнений.

идею необходимо реализовать . Если программу генерации худшего случая нужно написать на ТP ( в условиях ограничений на размер массивов), реализация идеи еще больше увеличивает сложность задачи.
При нахождении перестановки худшего случая потребуется массив длиной N.

N=70000 всё становится очень плохо. В ТP один массив не может занимать более 64 кб памяти, даже если он расположен в динамической памяти. И это уже не говоря о том , что под элемент нужно отводить не более 2байт.Решением может быть следующая нетривиальная конструкция из нескольких массивов, лежащих в динамической памяти:

value : longint);
Begin
A[index div 15000]^[index mod 15000]:= value;
end;
Function get (index : longint) : longint;
Begin
Get := a[index div 15000]^[index mod 15000];
End;
Begin for I := 0 to 4 do
New(a[i]);

6 1 3 5
3 6 1 2 4 5
4 6 1 2 5 3
5 2 1 6 4 3
5 2 6 3 4 1
5 3 1 6 2 4
5 3 6 4 2 1

значит и для 70000 можно найти такой
порядок цифр, букв и т.д. с помощью
представленного алгоритма…