Number of largest element exchanges for quicksort

Question

I'm improving my algorithms knowledge reading Robert Sedgewick "Algorithms" book and completing exercises. There's the one I have difficulties with:

What is the maximum number of times during the execution of Quick.sort() that the largest item can be exchanged, for an array of length N ?

I have determined experimentally, that the maximum number of exchanges of the largest item is floor(N/2), assuming all elements in array are distinct. How do I prove this mathematically? If I'm wrong, what's my mistake?

I have found several mentions of this question (such as this one), however, the answers do not match my results. That answers suggest the maximum number is N-1, but I wasn't able to find such an array, that will give me exactly N-1 exchanges of its largest item, when sorting it with my quicksort version (see below).

The code of quicksort that I use:

template<typename BiDirIterator, typename Compare = std::less<typename BiDirIterator::value_type>>
BiDirIterator partition(BiDirIterator begin, BiDirIterator end, Compare compare = Compare())
{
    auto partition_item = begin;
    while (true)
    {
        while (++begin != end && !compare(*partition_item, *begin));
        while (begin != end && !compare(*--end, *partition_item));

        if (begin == end)
            break;

        std::iter_swap(begin, end);
    }

    if (partition_item != --begin)
        std::iter_swap(partition_item, begin);

    return begin;
}

template<typename BiDirIterator, typename Compare = std::less<typename BiDirIterator::value_type>>
void quicksort(BiDirIterator begin, BiDirIterator end, Compare compare = Compare())
{
    if (begin == end || std::next(begin) == end)
        return;

    auto pos = partition(begin, end, compare);
    quicksort(begin, pos, compare);
    quicksort(++pos, end, compare);
}

And the code that I used to calculate the number of exchanges for the lasgest item:

struct exchange_counter
{
    exchange_counter(int value)
        : value(value)
    {
    }

    int value;
    int number_of_exchanges = 0;

    exchange_counter(const exchange_counter& other) = default;
    exchange_counter& operator=(const exchange_counter& other) = default;
    exchange_counter(exchange_counter&& other) = default;

    exchange_counter& operator=(exchange_counter&& other)
    {
        value = other.value;
        number_of_exchanges = other.number_of_exchanges + 1;
        return *this;
    }

    friend bool operator<(const exchange_counter& left, const exchange_counter& right) noexcept
    {
        return left.value < right.value;
    }

    friend bool operator==(const exchange_counter& left, const exchange_counter& right) noexcept
    {
        return left.value == right.value;
    }
};

for (int i = 1; i != 15; ++i)
{
    std::vector<exchange_counter> values;
    for (int j = 0; j != i; ++j)
        values.emplace_back(j);

    auto max_element = i - 1;
    auto max_number_of_exchanges = 0;
    do
    {
        for (auto& value : values)
            value.number_of_exchanges = 0;

        auto copy = values;
        quicksort(copy.begin(), copy.end());
        max_number_of_exchanges = (std::max)(max_number_of_exchanges,
            std::find(copy.begin(), copy.end(), max_element)->number_of_exchanges);
    }
    while (std::next_permutation(values.begin(), values.end()));

    std::cout << "Elements: " << i << "; max exchanges: " << max_number_of_exchanges << std::endl;
}

PS. If I test std::sort in Visual Studio 2015 (which is implemented as quicksort) using the same method, the number of exchanges of the largest item is N - 1.

Answer 1

The largest item must be moved by 2 positions each time we partition the array in order to exchange it the maximum number of times. It cannot be moved by just 1 position, because in this case it will become a pivot element and will be moved to its final position. For example, consider the following array:

4 10 3 x x x ...
P i  j

After partitioning the array the largest element (10) is moved by 1 position to the right

3 4 10 x x x ...
    P

But now the largest item becomes a pivot element and will be moved to the end of the array, adding only 1 exchange.

Instead, we need to arrange the items so that the largest item is moved by 2 positions keeping 1 item in front to become a pivot element:

2 10 4 1 x x x ...
P i    j

After partitioning:

1 2 4 10 x x x ...
    P i    j

The largest item is moved every time by 2 positions, therefore the number of exchanges is floor(N/2).

Example (N = 10)

2 10 4 1 6 3 8 5 7 9

The maximum number of times that the largest item (10) is exchanged is 5 in this case.