АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

4. Быстрая сортировка

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Для сортировки последовательности чисел широко используется быстрая сортировка - QSort. Ниже приведена программа, которая сортирует массив a, используя данный алгоритм.

var a : array [1..N] of integer;

procedure QSort(left, right : integer);
var m, i, j, t : integer;
begin
  m := a[(left+right) div 2];
  i := left; j := right;
  repeat
    while a[i] < m do inc(i); {первый while}
    while a[j] > m do dec(j); {второй while}
    if i <= j then
    begin
      t := a[i]; a[i] := a[j]; a[j] := t;
      inc(i); dec(j);
    end;
  until i > j;

  if j > left then QSort(left, j);
  if i < right then QSort(i, right);
end;

begin
  ...
  QSort(1, N);
end.

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

Исходные данные

Число N (1≤N≤70000)

Результат

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

Пример

Исходные данныеРезультат
31 3 2

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Сортировка и поиск /
4. 985. Двоичный поиск в упорядоченном массиве 1651. Закраска прямой - 2 1649. Инверсии-2
Учебные курсы / Структуры и алгоритмы / Сортировка данных и смежные темы /
4. 13. Инверсии 659. Отсортируйте список
 
время генерации 0.235 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.