QuickSort C++ Implmentation using Iterators #2

Question

This is part 2 of the previous question asked which is at - QuickSort C++ Implementation using Iterators.

Based on Jerry Coffin's answer, I have made the changes except for using templates.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>


typedef std::vector<int>::iterator itr;

itr partition(itr left,itr right)
{

    itr i=left-1;

    itr it=left;

    while(it<right)
    {
        if(*it<*right)
        {
            using std::swap;

            std::advance(i,1);
            swap(*i,*it);
        }
        std::advance(it,1);
    }

    using std::swap;

    swap(*(i+1),*right); 
    std::advance(i,1);
    return i;
}

void quicksort(itr left, itr right)
{
    if(std::distance(left,right)>=2)
    {
        itr q=partition(left,right);
        quicksort(left,q-1);
        quicksort(q+1,right);
    }
}


int main()
{
    std::vector<int> v={6,10,4,5,3,9,13,8};

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;

    quicksort(std::begin(v),std::end(v)-1);

    std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;


    return 0;
}

Answer 1

Interface:

quicksort(std::begin(v),std::end(v)-1);

I would write this so that you pass a begin/end (where end is one past the end) like the functions in std::. So that you can call it like this:

quicksort(std::begin(v),std::end(v));

Algorithm:

Your sort is not stable. ie if there are two values that are equal they maintain their relative order in the result (not so important with integers but can be useful with other types).

Type:

The sort only works with integers.

typedef std::vector<int>::iterator itr;

There is no need to limit your sort to only int you should be able to use any type that is comparable.

So just use this:

template<typename I>
I partition(I left,I right);

template<typename I>
void quicksort(I left, I right);

bug

If the value you are partitioning on is also the smallest (or largest) value then you get a bug. If the value you are partitioning is the smallest value. Then there will be zero values on the left side and thus q points at the partition value.

Then the following is invalid:

    quicksort(left,q-1);   // left and q-1 is a negatively sized partition.

Sorting this array:

std::vector<int> v={6,10,4,5,3,9,13,8,1};
                    // Added 1 here   ^

Results in this input:

6 10 4 5 3 9 13 8 1
1 3 5 4 6 9 8 10 13
    ^^^   ^^^

Correct Partition:

I could not do it off the top of my head.
So I translated this page into C++. I assume it is correct but don't know for sure.

template<typename I>
I partition(I l, I r)
{
    typename std::iterator_traits<I>::reference pivot = *l;
    I i = l;
    I j = r;
    --r;

    while(true)
    {
        do {
            ++i;
        }while( *i <= pivot && i <= r );
        do {
            --j;
        } while( *j > pivot );
        if( i >= j ) {
            break;
        }
        std::iter_swap(i, j);
    }
    // Unfortunately this line will break stability.
    // So this algorithm is not stable either.
    std::iter_swap(l, j);
    return j;
}

template<typename I>
void quickSort(I l, I r)
{
    if( l < r )
    {
        I j = partition(l, r);
        quickSort(l, j);
        quickSort(j+1, r);
    }
}

// Called as:
quickSort(std::begin(v),std::end(v));

Answer 2

You still have the same UB as in the original question. An unpleasant (i + 1) suggests the fix: first swap, then advance:

        itr i=left;
        itr it=left;

        while(it<right)
        {
            if(*it<*right)
            {
                using std::swap;

                swap(*i,*it);
                std::advance(i,1);
            }
            std::advance(it,1);
        }

        using std::swap;

        swap(*i,*right);
        return i;

Answer 3

If you're really going to limit your code to vectors of ints, then the using statement in

using std::swap;
swap(*(i+1),*right); 

is not accomplishing anything. You could just write

std::swap(*(i+1), *right);

since you always know the swapped elements are int. On the other hand, if you extend your code to support other types (that might specialize swap), then

using std::swap;
swap(*(i+1),*right); 

could be simplified to

std::iter_swap(i+1, right);