My version of C++ quicksort

I built my code according to the algorithm provided in this YouTube video. Please review it and help me find any problems. 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 problems?

#include 
#include 

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  leftbound) {
        int pivot = array[leftbound + (rand() % (rightbound - leftbound + 1))];
        int leftposition = leftbound;
        int rightposition = rightbound;
        while ( leftposition != rightposition ) {
            while ( array[leftposition]  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;
}

Please stop using:

using namespace std;

It may seem like a time saver. But for anything that isn't 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 
// Prefer
#include 

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 ) {
            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 ) {
            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(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 
#include 
#include 
#include 

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(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  pivot ) && (leftposition  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.
    }   
}

StackExchange Code Review Q#13635, answer score: 10