Худший случай для Быстрой сортировки

[frankenstein]

Здарова ребята!
Сидел июньским вечерком и решал задачки по программированию, для тренировки мозга, да и пальцы размять ;).
И вдруг, начались сложности с задачей. Задачка вроде простая, дан конкретный код быстрой сортировки:

void quick_sort(int * a, int left, int right, int & count) {
    int key = a[ (left + right) / 2 ];
    int i = left;
    int j = right;
    
    do {
        while (++count, a[i] < key) ++i;
        while (++count, key < a[j]) --j;
        
        if (i <= j) {
            swap(a[i], a[j]);
            ++i, --j;
        }
    } while (i <= j);
    
    if (left < j) quick_sort(a, left, j, count);
    if (i < right) quick_sort(a, i, right, count);
}

Надо найти перестановку элементов от $1$ до $N$, такую,
что на ней значение переменной count после работы сортировки будет максимальной.

Ясно что для быстрой сортировки, худший случай, когда она в качестве опорного элемента выбирает максимальный в подмассиве, который сортирует, в такой случае глубина рекурсии будет N. Но, я считаю, что одной теоретической информации о сортировке недостаточно чтобы решить данную задачу. Поэтому, я написал вот такой вот код:

#include <iostream>
#include <algorithm>
using namespace std;
 
void copy(int * a, int * b, int n) {
    for (int i = 0; i < n; ++i)
        b[i] = a[i];
}
 
int main() {
    const int a_size = 16;
    int a[a_size], b[a_size], c[a_size];
    
    for (int i = 0; i < a_size; ++i)
        a[i] = i+1;
        
    for (int size = 2; size <= 11; ++size) {
        sort(a, a+size);
        int count_max = 0, perm_num = 1, max_perm_num;
        do {
            int count = 0;
            copy(a, b, size);
            quick_sort(b, 0, size-1, count);
            if (count_max < count) {
               max_perm_num = perm_num;
               count_max = count;
               copy(a, c, size);
            }
            ++perm_num;
        } while (next_permutation(a, a+size));
        
        cout << size << " : " << count_max << endl;
        cout << max_perm_num << endl;
        for (int i = 0; i < size; ++i)
            cout << c[i] << ' ';
        cout << endl << endl;
    }
    {
        int n;
        cin >> n;
    }
   return 0;
}

В данной коде перебираются все перестановки, и выводится та, на которой сортировка сделала больше всего сравнений (значение count было максимальным)
Вывод данной программы:

        size: 2
       count: 3
perestanovka: 1
1 2 

        size: 3
       count: 6
perestanovka: 2
1 3 2 

        size: 4
       count: 12
perestanovka: 5
1 4 2 3 

        size: 5
       count: 19
perestanovka: 18
1 4 5 3 2 

        size: 6
       count: 27
perestanovka: 69
1 4 6 3 2 5 

        size: 7
       count: 36
perestanovka: 332
1 4 6 7 2 5 3 

        size: 8
       count: 46
perestanovka: 1899
1 4 6 8 2 5 3 7 

        size: 9
       count: 57
perestanovka: 12832
1 4 6 8 9 5 3 7 2 

        size: 10
       count: 69
perestanovka: 99297
1 4 6 8 10 5 3 7 2 9 

        size: 11
       count: 82
perestanovka: 871118
1 4 6 8 10 11 3 7 2 9 5 

Я предполагаю, что этих данных достаточно чтобы найти закономерность и научиться генерировать
худшие случаи для массивов больших размеров. Для данной задачи требуется сгенерировать массив
размера 70000.

Помогите мне найти закономерность.

[venco]

Плохо выбрать не только самый большой элемент, но и самый маленький.
Т.е. наихудших для этого варианта quicksort перестановок очень много - $2^{n-1}$. Некоторые из них имеют очень простую структуру.

[DanilovV]

frankenstein в сообщении #1029018 писал(а):

Но, я считаю, что одной теоретической информации о сортировке недостаточно чтобы решить данную задачу.

Решение кроется чуть выше.

frankenstein в сообщении #1029018 писал(а):

Ясно что для быстрой сортировки, худший случай, когда она в качестве опорного элемента выбирает максимальный в подмассиве, который сортирует, в такой случае глубина рекурсии будет N.

Осталось понять какой порядок выбора опорного элемента

[frankenstein]

venco в сообщении #1029028 писал(а):

Плохо выбрать не только самый большой элемент, но и самый маленький.
Т.е. наихудших для этого варианта quicksort перестановок очень много - $2^{n-1}$. Некоторые из них имеют очень простую структуру.

Да, наименьший тоже.
Я не могу определить эту вот структуру.

[Alexu007]

frankenstein в сообщении #1029018 писал(а):

Я предполагаю, что этих данных достаточно чтобы найти закономерность и научиться генерировать
худшие случаи для массивов больших размеров. Для данной задачи требуется сгенерировать массив
размера 70000.
Помогите мне найти закономерность.

Чё то больно мудрёно - то что вы предлагаете. Не проще ли сгенерировать реальный массив из 70000 цифр в случайном порядке, и сортировать его, выбирая в качестве опорного элемента разные числа: минимальное, близкое к минимальному, 1/4, 1/3, среднее, близкое к среднему, 2/3, 3/4, близкое к максимальному, максимальное. И смотреть как меняется требуемое для каждого случая число перестановок.

[frankenstein]

Alexu007
дело в том что код сортировки, по условию задачи, нельзя менять.
А если сгенерировать случайный массив, нет 100% гарантии, что
на нем сортировка сработает худшим образом.

[venco]

frankenstein в сообщении #1029074 писал(а):

Да, наименьший тоже.
Я не могу определить эту вот структуру.

Ну я вот попробовал наобум чередовать минимальный и максимальный элементы, и получилость нечто очень регулярное. Но вам придётся разобраться в алгоритме, что же именно он делает с массивом в таких случаях.

[slavav]

Вы можете ухудшить массив который сортируете. Для этого надо в каждый элемент надо добавить его индекс в исходном массиве. Назовём такой индекс исходным. Всякий раз когда сортировка выбирает ключ, печатайте исходный индекс. Берёте первый напечатанный исходный индекс и на это место записываете максимальный элемент в массиве. Снова запускаете сортировку. На место второго напечатанного исходного индекса записываете второй по величине элемент в массиве. И так далее. Надо только помнить, для определения следующего исходного индекса надо заново прогнать сортировку, так как изменение значения в текущем исходном индексе меняет все последующие распечатанные исходные индексы. Эту процедуру можно превратить в алгоритм, который за $N^3$ найдёт наихудший массив длины $N$. Небольшая оптимизация поможет сократить время до $N^2$.