QuickSort C++ Implementation using Iterators

Question

I implemented quicksort using iterators. I am will be grateful, if someone can review my piece of code. BTW, I am just selecting the last element as the pivot (which I plan to randomize later) I am mainly looking for the following:

1) Correctness of the Implementation

2) Correct usage of iterators

3) Basic coding style.

Although above are the key things I am looking for, please feel free to point out any mistakes. Thanks!!!

#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)
 {
 ++i;
 std::swap(*i,*it);
 }
 ++it;
 }
 std::swap(*(i+1),*right); 
 return ++i;
}
void quicksort(std::vector<int>& v,itr left, itr right)
{
 if(std::distance(left,right)>=2)
 {
 itr q=partition(left,right);
 quicksort(v,left,q-1);
 quicksort(v,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(v,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;
}

• Mast: I have rolled back the last edit. Please see What to do when someone answers .
• AlexanderTG: @Mast I have posted a new question, to get more feedback and I will remember the rules. Thanks for letting me know.

Answer 1

Templates

Sorting is pretty much the same regardless of the type of items being sorted, as long as you can compare and swap those things. Might as well implement the sorting and partitioning as templates so they can work for various containers and/or types in the containers.

Pass only what's needed

Right now, your quicksort receives the container to be sorted as a parameter. It also receives iterators referring to the beginning and end of the range to be sorted. It "uses" the container parameter only to pass it in further recursive calls--but none of the calls ever actually makes any real use of that parameter.

The parameter is never used, so you might as well not pass it.

At the same time, sorting an entire collection is common enough that it may well be worthwhile to provide that directly. For example:

// basic version that uses (only) iterators
template <class Itr>
void quicksort(Itr b, Itr e) {
 if (std::distance(b, e) > 1) {
 Itr pivot = partition(b, e);
 quicksort(b, pivot);
 quicksort(pivot, e);
 }
}
// Version to sort a whole container
template <class Container>
void quicksort(Container &c) { 
 quicksort(c.begin(), c.end());
}

Don't explicitly specify std::swap

If the user has defined a swap for the type of object being sorted, you want to use it. You only want to use std::swap if they haven't defined it. To do that, you typically have a using directive to make std::swap visible in the current scope, then make an unqualified call to swap. If they've defined a swap for their type, this will find their swap via argument dependent lookup. Then, if (and only if) that fails, it will find std::swap.

if(*it<=*right)
{
 using std::swap;
 ++i;
 swap(*i,*it);
}

Decide what to support

Right now, you use std::distance to measure the distance between a pair of iterators. That lets the code work with most categories of iterators.

Unfortunately, you also use iterator + int, and that only works with random access iterators, so the code overall only works with random access iterators.

If you don't mind requiring random access iterators, then you might as well depend on them throughout, and just subtract iterators to get a distance.

Conversely, if you really want the code to work with other iterators, you should truly support that, such as by using std::advance or std::next to modify the pointers.

Minimize requirements on the contained type

Quicksort can be written so the only comparison it depends upon is operator<. Right now you use <= for no particularly good reason that I can see.

• AlexanderTG: I made changes based on your suggestions. The code is here- codereview.stackexchange.com/questions/134896/…. Thanks.

Answer 2

• There is no need to pass the vector itself. Iterators provide just enough information (notice that the real work is done by partition algorithm, and it doesn't need v).

• partition doesn't look correct: i = left - 1 is an invalid iterator when left is v.begin(). It doesn't matter that you never dereference it, mere computation is an undefined behaviour.

• Semi-open ranges are usually more convenient than closed ones.

• AlexanderTG: I get what you are saying about the the variable i in the partition function being invalid iterator but can you suggest a better way to do it ? Thanks!!!