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

• 1 слайд

  Презентация решения
  Олимпиадных задач
  по программированию
  
  
  

• 2 слайд

  Олимпиадная Задача
  ‘’Анти-быстрая сортировка‘’
  Объём памяти, предоставляемый программе,
  составляет 500 кб!!!
  

• 3 слайд

  Все вы знаете, или догадываетесь…
  О существовании Алгоритма быстрой сортировки…
  Но не все знают что он не так быстр на больших числах…
  

• 4 слайд

  key := a[(left + right) div 2];
  i := 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;
  

• 5 слайд

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

• 6 слайд

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

• 7 слайд

  Решение AQSORT;
  
  Темы: перебор n!, динамическая память TP.
  

• 8 слайд

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

• 9 слайд

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

• 10 слайд

  Var a,b:array[1..7] of integer;
  В массиве b будем генерировать перестановки, потом копировать содержимое массива b в массив a, потом сортировать. Теперь о том, как подсчитывается количество сравнений. Нужно объявить переменную целого типа, обнулять ее каждый раз, когда массив b копируется в a, и увеличивать на единицу при каждом выполнении цикла while и при каждом выходе из цикла while:
  

• 11 слайд

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

• 12 слайд

• 13 слайд

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

• 14 слайд

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

• 15 слайд

  Type L15k=array[0..14999] of longint;
  Var a : array[0..4] of ^L15k;
  Procedure put (index, 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]);
  
  

• 16 слайд

  Пример ввода вывода:
  len=6 max=27
  1 4 6 3 2 5
  2 4 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
  
  

• 17 слайд

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