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));

• AlexanderTG: Thanks, for pointing out the bug I totally missed it. I am also unsure as to how I can fix that. I tried a couple of things but they are not working. Also, I tried changing interface to quicksort(std::begin(v),std::end(v)); but that ended up giving me 0 in the beginning because of the reason you mentioned that left and q-1 are not valid. The most weird part is also when I add 1 at the end and the interface you suggest, I get the following output - interface : qicksort(std::begin(v),std::end(v)); and input {6,10,4,5,3,9,13,8,1}, output :- 0 1 3 4 5 6 8 9 10

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;

• AlexanderTG: Great, clever way to do it. I also added in your suggestions.

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);

• AlexanderTG: I incorporated your suggestions, I totally forgot about iter_swap, and yes I am only supporting it for ints by design and plan to change it later, as I want to confirm that my implementation of the algorithm is flawless.