Решение задачи Анти-QuickSort с Меньшиков

Без пояснения   Просмотров: 222


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

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

procedure QSort(left, right : integer);
var
i, j : integer;
key : integer;
buf : integer;
begin
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;

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

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

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n;
vector<int> mas;
void input()
{
    cin>>n;
    mas.resize(n);
    for (int i=0;i<n;i++)
        mas[i] = i+1;
}
void solve()
{
    for (int i=2;i<n;i++)
        swap(mas[i],mas[i/2]);
}
void output()
{
    for (int i=0;i<n;i++)
        printf("%d ",mas[i]);
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    output();
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться