My own quicksort algorithm

Question

I will make it more reader friendly after I get the algorithm completed. Does anything with the quick sort algorithm stand out as for why it is not working 100%? This is not homework; I am just practicing problems out of books and I am caught on this one.

Hints, more so than answers, would be more appreciated. Please don't post your own quick sort algorithm, as copying someone else's code does not help me learn. I am just looking for that last bit to help me make the leap across; I don't want you to build another bridge somewhere else, and say "use mine"; it won't help. If my algorithm is a lost cause just say so, and I will go back to the drawing board.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <ctime>
#include <assert.h>

using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::ostream_iterator;
using std::istream_iterator;

void print_part( vector<float>::iterator l,
                 vector<float>::iterator r ) {
    copy( l,r+1,ostream_iterator<float>( cout," " ) );
    cout << endl;
}

void print( std::vector<float> &data ) {
    copy( data.begin( ), data.end( ), 
          ostream_iterator<float>( cout," " ) );
    cout << endl;
}

void swap( vector<float>::iterator left,
           vector<float>::iterator right ) {
    cout << "Swaping " << (*left) << " with " << (*right) << endl;
    float tmp = (*right);
    (*right) = (*left);
    (*left) = tmp;
}

int get_pivot_index( vector<float> &data,
                     vector<float>::iterator left,
                     vector<float>::iterator right ) {
    int pivot_index = ((right-left)/2);
    int base = std::distance( data.begin( ),left );
    return ( pivot_index+=base );

}

void my_qsort( vector<float> &data, 
               vector<float>::iterator left,
               vector<float>::iterator right,
               int side
             ) {
     ((side==0) ? cout<<"":(side==1) ? cout<<"Left: " : cout<<"Right: " );
     print_part( left,right );
     if( (right-left)>0) {
         vector<float>::iterator lit=left;
         vector<float>::iterator rit=right;
         int pivot_index = get_pivot_index( data,left,right );
         int pivot=data[pivot_index];
         cout << "pivot = " << pivot << endl;
         while( lit <= right && rit > left && lit <= rit ) { 
             while( lit <= right && (*lit) < pivot ) {
                 if( lit > rit ) { break; }
                 else { lit++; }
             }
             while( rit > left && (*rit) >= pivot ) { 
                 if( lit > rit ) { break; }
                 else { rit--; }
            }
            if( lit < rit ) { swap( lit,rit ); }
        }
        my_qsort( data,left,rit,1 );
        my_qsort( data,lit+1,right,2 );
    }
    char c;
    cin >> c;
}

int main( int argc, char *argv[ ] ) {
    vector<float> 
    data( 
          ( istream_iterator<float>( cin ) ),
          ( istream_iterator<float>( ) )
        );
    cout << "-----------------------------------------------" << endl;
    my_qsort( data,data.begin( ),data.end( )-1,0 );
    cout << "-----------------------------------------------" << endl;
    print( data );
    return ( 0 );
}

Answer 1

1. I will ask myself -- "What are the invariants?" and use assertions to make sure the invariants are satified by the code. In this case, my_qsort should return a sorted range.

2. I will try to find the simplest failing example to understand what is going wrong.

Answer 2

• The last three libraries should be removed as they're not being used. There's no need to keep a library around if you're long longer using it or have never used even it.

  You may also consider organizing them in some way, such as alphabetically.

• You don't really need these:

  using std::vector;
  using std::cin;
  using std::cout;
  using std::endl;
  using std::vector;
  using std::ostream_iterator;
  using std::istream_iterator;
  

  Just use std:: where needed, otherwise it'll just get longer if you add more. Also, you have listed using std::vector twice, but it should just be there once.

• print() isn't modifying any data members (it just prints something):

  print( std::vector<float> &data )
  

  so data should be passed by const& to avoid an unnecessary copy:

  print(std::vector<float> const& data)
  

• There's no need to provide your own swap() function; just use std::swap:

  std::swap(lit, rit);
  

• This is not a very common nor maintainable style in my_qsort():

  if( lit > rit ) { break; }
  else { lit++; }
  

  Put each bracketed statement on its own line, in case you ever need to add to them:

  if (lit > rit) {
      break;
  }
  else {
      lit++;
  }
  

• Why is there a "pause" in my_qsort()?

  char c;
  cin >> c;
  

  Just let the function works without such interruptions. But if you must keep it anyway, then at least make the user aware that it's a pause, and tell them to input a character in order to continue.

• Using parentheses for a simple return is not really needed:

  return ( 0 );
  

  Just keep it simple and omit them:

  return 0;
  

  Moreover, you don't really need this. Reaching the end of main() already implies success, so the compiler will insert the return itself.

Answer 3

I have a couple of suggestions.

1. Don't wait until you are finished to make your code reader friendly. That's a bad habit to develop because of situations like the one you are in now. You'd like someone else to look at your code but it's not as easy to read as it should be, so it's hard to get the help you'd like. Also, once you start coding for a living there will be pressure to not "waste time" cleaning up something that already works.

2. You didn't mention how you know you have a problem. Does it work on some data sets and not others? If so, what's different between the data sets? If you are testing with large data sets you may have a hard time seeing the key difference. Start your testing with very small data sets: 1, then 2, then 3 elements (using all the permutations of starting order). Small data sets can be traced by hand.

Answer 4

The mistake lies in your left sort. When the 1st value is greater than 2nd value your sort does not work. So focus on that part of your code. Normally these kind of problems are very small and easy to fix but hard to spot :-)

Also would be interesting to see how you sort 4 and 5 characters that are shuffled differently as it would highlight the left side sort issue :-)

If you need more specific help then let me know