My version of C++ quicksort

Question

I built my code according to the algorithm provided in this YouTube video. http://www.youtube.com/watch?v=y_G9BkAm6B8

The file attached is my code, please review it and help me find the problem. It definitely takes a lot longer than the qsort function in C++. But the algorithm I use should be just as fast. Can anyone find the problem?

#include <iostream>
#include <time.h>

using namespace std;

void randomize( int* array, int size );
void qsort( int* array, int leftbound , int rightbound );
void swap( int &a, int &b );
void output( int* array, int size );

int main()
{   
    //declare array
    int array[100];

    //get size of the array
    int size = sizeof(array)/sizeof(int);

    //randomize value
    randomize(array, size);

    //start the quicksort algorithm
    qsort(array, 0, size-1 );

    //output the array
    output(array, size);

    return 0;
}

void randomize( int* array, int size )
{
    srand((int)(time(0)));
    for ( int i = 0 ; i < size ; i++ ) {
        array[i] = rand();
    }
}

void output( int* array, int size )
{
    for ( int i = 0 ; i < size ; i++ ) {
        cout << array[i] << endl;
    }
}

void qsort( int* array, int leftbound , int rightbound )
{
    if (rightbound > leftbound) {
        int pivot = array[leftbound + (rand() % (rightbound - leftbound + 1))];
        int leftposition = leftbound;
        int rightposition = rightbound;
        while ( leftposition != rightposition ) {
            while ( array[leftposition] < pivot ) {
                leftposition++;
            }
            while ( array[rightposition] > pivot ) {
                rightposition--;
            }
            swap ( array[leftposition], array[rightposition] );
        }
        qsort( array, 0, leftposition - 1 );
        qsort( array, leftposition + 1, rightbound );
    }
}

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

Answer 1

Please stop using:

using namespace std;

It may seem like a time saver. But for anything that it is not a toy program it causes problems with collisions. So it is a bad habit to get into. Stop before it becomes a habit.

You have alternatives.
You can selectively bring stuff into the current scope:

using std::cout;
using std::vector;

Alternatively (my preference) you prefix stuff in the the standard library with std::. The name std was chosen so it was short enough that people would not be hampered with typing it.

Prefer to use the C++ version of the headers:

#include <time.h>
// Prefer
#include <ctime>

Note: This also puts the functions in the standard namespace.

This is correct:

int size = sizeof(array)/sizeof(int);

But it makes the code brittle. If you change the type of the array. You also need to remember to change type here in the size expression. It is best to let the compiler deduce this so use:

int size = sizeof(array)/sizeof(array[0]);

Usage:

qsort(array, 0, size-1 );

Here you are making right bound point at the rightmost item. In C++ it is so common that the end points one past the end of the data it may make the code slightly harder to grok. I would stick with the standard convention of pointing one past the end. This means there will be some adjustment in your qsort but not that much and it makes it easier for C++ users to read.

Prefer pre-increment:

++leftposition;  // rather than leftposition++;

Though it makes no difference in this situation. There are situations where it can. So it one of those habits you should get into. Then when the types of objects are changed you do not need to search your code to make sure you are using the efficient version you know you used the efficient version automatically.

Your test for a sortable array is not aggressive enough:

if (rightbound > leftbound) {

You only don't sort if the array is zero length. Which may potentially lead to long recursion as you randomly choose a pivot point that always dives stuff to one side (luckily your non standard code below saved you by always leaving the pivot off subsequent sorts).

The real answer is you only need to sort arrays that have a size >= 2. (size zero and one are already sorted).

if ((rightbound - leftbound /* +1 depending on if you rightbound is one past or not*/ ) >= 2)

Small difference from a standard implementation here:
Which can potentially give you an infinite loop.

        while ( array[leftposition] < pivot ) {
            leftposition++;
        }
        while ( array[rightposition] > pivot ) {
            rightposition--;
        }

What happens if the value is equal to the pivot. In that case it will go to a random side. Also if both left and right side hit a value that is equal to pivot then you will swap them and restart the loop which will do nothing swap them and restart the loop (etc)

        while ( array[leftposition] <= pivot ) {
            leftposition++;
        }
        while ( array[rightposition] > pivot ) {
            rightposition--;
        }

Your left bound of the first recursive call is wrong.

    qsort( array, 0, leftposition - 1 );
    qsort( array, leftposition + 1, rightbound );

Should be leftbound.

    qsort( array, leftbound, leftposition - 1 );
    qsort( array, leftposition + 1, rightbound );

Since there can potentially be more than one value equal to pivot. Maybe you can remove the all from the side you put them in.

You need to look at the standard libs.

We have a std::swap()

void swap(int &a, int &b)

// use 
std::swap(val1, val2)

We have a way to print stuff:

void output( int* array, int size )

// use
std::copy(std::begin(array), std::end(array), std::ostream_iterator<int>(std::cout, "\n")); 

We have a way to generate values:

void randomize( int* array, int size )

// use
generate(std::begin(array), std::end(array), ::rand);

This is what I got:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <ctime>

void qsort( int* array, int leftbound , int rightbound );

int main()
{   
    //declare array
    int array[100];

    //get size of the array
    int size = sizeof(array)/sizeof(array[0]);

    //randomize value
    std::srand(std::time(NULL));
    std::generate(std::begin(array), std::end(array), std::rand);

    //start the quicksort algorithm
    qsort(array, 0, size);

    //output the array
    std::copy(std::begin(array), std::end(array), std::ostream_iterator<int>(std::cout, "\n"));
}

void qsort( int* array, int leftbound , int rightbound )
{
    if ((rightbound - leftbound) >= 2)
    {   
        int pivot = array[leftbound + (rand() % (rightbound - leftbound))];
        int leftposition    = leftbound;
        int rightposition   = rightbound - 1;

        while ( leftposition < rightposition )
        {   
            while ((array[leftposition] <= pivot) && (leftposition < rightposition))
            {   ++leftposition;
            }   
            while ((array[rightposition] > pivot ) && (leftposition < rightposition))
            {   --rightposition;
            }   
            std::swap(array[leftposition], array[rightposition]);
        }
        // At least the pivot point will be on the left hand side.
        // This will also be the largest value. So move the leftposition back
        // to remove all the pivot points.
        while(((leftposition-1) > leftbound) && (array[leftposition-1] == pivot))
        {   --leftposition;
        }
        qsort(array, leftbound, leftposition-1);    // leftposition is one past the end of the left
        qsort(array, rightposition+1, rightbound);  // Thus at the start of the right.
    }   
}

Answer 2

The first major problem I see is that you're not considering rightposition when incrementing leftposition and vice versa. This can cause L and R to cross, which will cause additional unnecessary swaps:

pivot value 7

4,7,3,9,6,2,8,1
  L           R      
4,7,3,9,6,2,8,1
      L   R     //<--this is the last swap that should happen, but L < R
4,1,3,9,6,2,8,7
          L     //...so L moves to the next value greater than the pivot
4,1,3,2,6,9,8,7
        R L     //...and R moves to the next value less than the pivot
4,1,3,2,6,9,8,7
        R L     //...which are swapped incorrectly
4,1,3,2,9,6,8,7

I'm going to assume that the != in the main pivoting loop is a typo, because combined with the lack of checking that the positions don't cross, the positions would be incremented beyond the ends of the array and the whole thing would error out.

leftposition and rightposition should NEVER cross. In addition, even if they don't and you miraculously end up with both leftpos and rightpos on the same element (which would have to be the pivot), you swap that element with itself unnecessarily; don't do that.

Finally, in your code the "left half" call always starts at index zero; that means that the left-half call that branches from all right-half calls will scan through the entire left-hand side of the array, not just of the half it should have been given. Because the left half is sorted first, there should be no swaps, but it still has to scan through all those elements, which makes the right-hand half of the algorithm approach O(N²) complexity.

Try this:

void qsort( int* array, int leftbound, int rightbound )
{
    if (rightbound <= leftbound) return; //reduce nesting

    int pivotIndex = leftbound + (rand() % (rightbound - leftbound + 1);
    int pivot = array[pivotIndex];

    //move the pivot value out of the way; we will discover where it goes
    swap(array[pivotIndex], array[rightbound]);

    int leftposition = leftbound;
    int rightposition = rightbound-1;

    //you could use the != here if you really wanted, WITH the changes inside the loop
    while ( leftposition < rightposition ) 
    {
        //don't move leftpos past rightpos
        while ( array[leftposition] < pivot && leftposition < rightposition) 
           leftposition++;

        //ditto
        while ( array[rightposition] > pivot && rightposition > leftposition )
           rightposition--;

        //don't swap if the two positions have merged
        if(leftposition < rightposition)
           swap ( array[leftposition], array[rightposition] );
    }

    //now, swap the pivot element back in; leftposition is its proper location.
    swap(array[rightbound], array[leftposition]);

    //No matter what, leftposition (and rightposition) will be at an element 
    //that should be to the right of the pivot, so the swap works. 
    //Trace it out yourself if you don't believe me.

    //here's your main inefficiency; you were always starting from index 0 
    //on the left side, meaning that the call for the "left half" of all 
    //"right half" calls scans most of the array redundantly.
    qsort( array, leftbound, leftposition - 1 );
    qsort( array, leftposition + 1, rightbound);    
}

I'm sure there are some additional micro-optimizations that could be made here:

• since we're making the leftpos vs rightpos check in all the right places, we could use != instead of < everywhere which would probably be faster.
• The prefix increment operation is performed assuming that the existing value isn't needed for any further operation, and so it just happens, making it faster than the postfix increment.

However, the algorithm above will perform correctly which is the primary goal.