Quicksort application

Question

What do you think about this code?

#include <iostream>
using std::cout;
using std::endl;

#include <vector>
using std::vector;

#include <ctime>
#include <cstdlib>

template < typename T >
vector < T > concatenate( vector < T > _a_, T piv, vector < T > _b_ )
{
  vector < T > v_list;
  v_list.insert( v_list.begin(), _a_.begin(), _a_.end() );
  v_list.push_back( piv );
  v_list.insert( v_list.end(), _b_.begin(), _b_.end() );
  return v_list;
}

template < typename T > 
vector< T > quick( vector< T > vec )
{
  vector< T > v_less, v_greater, v_list;
  vector< T > aux1, aux2;
  typename vector < T >::const_iterator iter_Const;
  if( vec.size() <= 1 )
    return vec;
  int piv = *(vec.end() - 1);
  vec.pop_back();
  for( iter_Const = vec.begin(); iter_Const != vec.end(); ++iter_Const )
  {
    if( *iter_Const < piv )
      v_less.push_back( *iter_Const );
    else
      v_greater.push_back( *iter_Const );  
  }
  return concatenate( quick( v_less ), piv, quick( v_greater ) );  
}

int main() {
  vector < int > lista;
  srand( 1 );
  cout << "VECTOR" << endl;
  for( int i = 0; i < 10000; i++ )
  {
      lista.push_back( rand() % 100 );
      cout << lista[i] << " | ";
  }
  cout << endl;
  cout << "******" << endl;
  cout << "QUICKSORT" << endl;
  lista = quick( lista );
  vector < int > :: const_iterator it;
  for( it = lista.begin(); it != lista.end(); ++it )
    cout << *it << " | ";
  cout << endl;
}

Answer 1

If this is not just a learning exercise, I have to point out that C++ already has a sorting function in its standard library and in real code you should use that. So for the rest of this answer I'm going to assume that this is in fact just a learning exercise.

Now first a note on the algorithm: Usually quicksort is implemented in-place for better performance. Even if you want a sorting function which does not modify its argument, it's quicker to just copy the argument and then run an in-place quicksort on the argument.

Further you're creating a lot more copies of your vectors than you need to, even when using this choice of algorithm: Every time you pass a vector by value, it is copied. Every time you pass a vector, which you do not want to modify, you should rather pass it by const reference, so as not to create an unnecessary copy.

On the same note concatenate also creates an unnecessary copy by returning the result vector by value. This can be avoided by passing an empty vector by non-const reference and filling that instead of using a return value.

Lastly there is a bit of code duplication in your main function: You're printing a vector separated by pipes twice - once during its creation and once after sorting. I would define a helper function print_vector, which prints a vector separated by pipes, and call that twice: once after creating the vector and once after sorting it. This way the first printing will have to happen after the vector creation, not during, but that's okay as doing it during the creation gives very little performance benefit (if any) and having the creation be a separate step from printing the vector improves code cleanliness.

Answer 2

To add to sepp's answer, there are also some other finer points worth mentioning:

Considering the worse-case. Your current implementation always uses the last element of the vector as the pivot. The worse-case is easily triggered by feeding it a sorted/reversed sorted vector turning your quicksort into a O(n^2) selection sort.

Your quicksort can offer more flexibility by just changing it to accept a starting and ending range to sort rather than just taking the vector directly. e.g. you might want to sort from elements x to y making up a subrange of vector rather than the entire vector.size().

The basic steps for any quicksort implementation is this:

• Choose a pivot.
• Partition the elements around this pivot giving a low partition and a high partition.
• Quicksort the lower partition.
• Quicksort the higher partition.

With those steps in mind you can rewrite your quicksort so that the code is clearer, like so:

namespace practice{

template <typename T>
T partition(const T &start, const T &end);

template <typename T>
void quicksort(const T &start, const T &end)
{
  // empty range?
  if(start == end) return;

  // start by partitioning the range to sort
  // and saving the pivot used.
  T pivot = partition(start, end);

  // now just sort the low and high partitions
  quicksort(start, pivot);
  quicksort(pivot + 1, end);
}

}

The real work is happening in partition so I'll leave that part for you to handle. As Sepp said though, one of the highlights of quicksort is that it can be performed in-place.

To do that you need to know where the lower partition ends and the higher begins. You can keep track of that with an extra pointer variable, firsthigh(or alternatively lastlow). In your partition function your range will then have 3 parts: lower partition (start to firsthigh), higher partition(firsthigh to current_element) and the unprocessed range(current_element to end). As your partition function works through the range the unprocessed gets smaller obviously. If the current element belongs in the high partition do nothing and move to the next element. If it belongs in the low partition just swap with firsthigh. Increment firsthigh by one to maintain the invariant.

Hopfully that's enough detail to help you rewrite your qsort better.

Answer 3

I caught a couple of stylistic issues.

Having both worked on inherited code and had to debug my own code after a couple of years, my first comment is the total lack of comments in the code. What was clear to you at 1 am in the morning may make no sense after you wake up at 10 am. It may make even less sense when you have to debug it after 2 years.

Consider at a minimum commenting your templates and method declarations. I would also suggest commenting your basic steps as well (see Victor T's response).

The other issue may seem like a small thing, but I have seen it cause some serious problems, especially when people go into make "quick fixes" to existing code.

Here's the genesis of the problem.

The original code:

// ** do something **
if (a.some_value < b.call_a_func(c))
    a.some_value = 3;
// ** do something else **

The patched code:

// ** do something **
if (a.some_value < b.call_a_func(c))
    a.some_value = 3;
    call_another_func(a);
// ** do something else **

What the patched code was suppose to be:

// ** do something **
if (a.some_value < b.call_a_func(c))
{
    a.some_value = 3;
    call_another_func(a);
}
// ** do something else **

If the original developer had used braces around the 1 line condition, the bug in the patched code may not have been introduced.