> Здравствуйте, Буравчик, Вы писали:

Перестановки, на которых алгоритм производит максимум сравнений приводят и к максимальной глубине рекурсии.
Единственный момент, на который нужно обратить внимание — перестановка {2,1} дает меньше сравнений, чем {1,2}. Поэтому обменяем 1 и 2 в результирующей перестановке.

vector<int> find_adversary(const int n)
{
    vector<int> data(n);
    vector<pair<int, int> > pairs;

    // Maintain original positions.
    for(int i = 0; i < n; ++i)
        data[i] = i;

    // At each step data[k/2] contains initial position after reverse (n-(k+1)) qsort applications.
    // Set it to maximal value.
    for(int k = n - 1; k >= 0; --k)
    {
        pairs.push_back(make_pair(k, data[k/2]));
        swap(data[k/2], data[k]);
    }

    vector<int> result(n);

    for(int i = 0; i < n; ++i)
    {
        result[pairs[i].second] = pairs[i].first + 1;
    }

    // Just swap 1 and 2 in result permutation due to the fact that {1, 2} gives 3 and {2, 1} gives 2 comparisons.
    swap(*find(result.begin(), result.end(), 1), *find(result.begin(), result.end(), 2));

    return result;
}

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

int main()
{
    const int answers[] = {3, 6, 12, 19, 27, 36, 46, 57, 69, 82}; 

    for(int i = 0; i < sizeof(answers)/ sizeof(answers[0]); ++i)
    {
        const int n = i + 2;
        vector<int> adversary = find_adversary(n);
        int count = 0;
        quick_sort(adversary, 0, n-1, count);

        if (count != answers[i])
            cout << "Case #" << i << ": FAILED!" << " Expected: " << answers[i] << " Received: " << count << endl;
        else 
            cout << "Case #" << i << ": PASSED!" << endl;

    }
}

> Здравствуйте, Буравчик, Вы писали:

Перестановки, на которых алгоритм производит максимум сравнений приводят и к максимальной глубине рекурсии.
Единственный момент, на который нужно обратить внимание — перестановка {2,1} дает меньше сравнений, чем {1,2}. Поэтому обменяем 1 и 2 в результирующей перестановке.

vector<int> find_adversary(const int n)
{
    vector<int> data(n);
    vector<pair<int, int> > pairs;

    // Maintain original positions.
    for(int i = 0; i < n; ++i)
        data[i] = i;

    // At each step data[k/2] contains initial position after reverse (n-(k+1)) qsort applications.
    // Set it to maximal value.
    for(int k = n - 1; k >= 0; --k)
    {
        pairs.push_back(make_pair(k, data[k/2]));
        swap(data[k/2], data[k]);
    }

    vector<int> result(n);

    for(int i = 0; i < n; ++i)
    {
        result[pairs[i].second] = pairs[i].first + 1;
    }

    // Just swap 1 and 2 in result permutation due to the fact that {1, 2} gives 3 and {2, 1} gives 2 comparisons.
    swap(*find(result.begin(), result.end(), 1), *find(result.begin(), result.end(), 2));

    return result;
}

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

int main()
{
    const int answers[] = {3, 6, 12, 19, 27, 36, 46, 57, 69, 82}; 

    for(int i = 0; i < sizeof(answers)/ sizeof(answers[0]); ++i)
    {
        const int n = i + 2;
        vector<int> adversary = find_adversary(n);
        int count = 0;
        quick_sort(adversary, 0, n-1, count);

        if (count != answers[i])
            cout << "Case #" << i << ": FAILED!" << " Expected: " << answers[i] << " Received: " << count << endl;
        else 
            cout << "Case #" << i << ": PASSED!" << endl;

    }
}