Quicksort using first element pivot

Question

I'm trying to get my Quicksort implementation doing fewer comparisons. The first element is used as a pivot. Could you give me some directions if there are any places that should be optimized in a sense of making fewer comparisons? As I understand, it's due to a redundant recursion pass, since the partition subroutine and comparisons counting in it are implemented correctly.

#include <vector>

using namespace std;
using uint = unsigned int;

uint PartitionSub(vector<uint>& inp, uint l, uint r, uint& numOfCmp);

void QuickSort(vector<uint>& inp, uint l, uint r, uint& numOfCmp)
{
    if (r - l < 2)
        return;

    uint newPivotIdx = PartitionSub(inp, l, r, numOfCmp);

    QuickSort(inp, l, newPivotIdx, numOfCmp);
    QuickSort(inp, newPivotIdx + 1, r, numOfCmp);
}

uint PartitionSub(vector<uint>& inp, uint l, uint r, uint& numOfCmp)
{
    auto swap = [&inp](uint a, uint b)
    {
        uint buf = inp[a];
        inp[a] = inp[b];
        inp[b] = buf;
    };

    //numOfCmp += r - l; // we can use this, but ++numOfCmp just before     
                         // comparison is more clear
    uint i = l + 1;
    uint j = l + 1;

    uint p = inp[l];

    for (; j <= r; j++)
    {
        ++numOfCmp;
        if (inp[j] <= p)
        {
            if (i != j)
                swap(i, j);
            i++;
        }
    }

    uint newPivotIdx = i - 1;
    swap(l, newPivotIdx);
    return newPivotIdx;
}

Answer 1

Prefer standard integer types

Instead of:

using uint = unsigned int;

Prefer

#include <cstdint>
//use the std::uint32_t in code (or whichever width)

Don't use namespace std

Common advice which will help guard against namespace collisions. In your case I think you could get away with just:

using std::vector;

Quicksort Algorithm

A common optimization to remove average case comparisons is to more intelligently select your pivot. One approach which strengthens the asymptotic runtime of the algorithm is the 'median of fives' approach. In this approach you select your pivot to be the median of 'the median of each of the n/5 sublists of length 5'. In practise, however, this could increase the number of comparisons. It's hard to recommend a strategy without knowing the size and characteristics of your input.

Answer 2

Follow standard conventions

C++ standard algorithms follow a convention of using iterators to define ranges on which to work. Rather than passing a container pass two iterators to define a range.

Secondly you should be able to sort anything (that is comparable (defines operator<)) not just integers. If you want to be flashy allow a function to be passed that knows how to compare objects (but that is a phase two just assume that you can compare any type with operator< and the compiler will let you know when that is not true).

// Rather than this:
void QuickSort(vector<uint>& inp, uint l, uint r, uint& numOfCmp)

// Define it like this:
template<typename I>
void QuickSort(I begin, I end);

Dont use this:

using namespace std;

see: Why is “using namespace std” in C++ considered bad practice? and Answer 2

There is already a std::swap

    auto swap = [&inp](uint a, uint b)
    {
        uint buf = inp[a];
        inp[a] = inp[b];
        inp[b] = buf;
    };

Just use the standard swap std::swap() there is even one that works on iterators std::iter_swap().

Not convinced that algorithm is correct.

Normally when I see the pivot/partition I see the code scanning from left and right towards the middle. Here I see a scan from left to right only. But it seems to work.

    //numOfCmp += r - l; // we can use this, but ++numOfCmp just before     
                         // comparison is more clear
    uint i = l + 1;
    uint j = l + 1;

    uint p = inp[l];

    for (; j <= r; j++)
    {
        ++numOfCmp;
        if (inp[j] <= p)
        {
            if (i != j)
                swap(i, j);
            i++;
        }
    }