Is this C++ quicksort program okay?

Question

I wrote a quicksort program in C++.

1. Is it okay to implement it this way?
2. Am I using pointers correctly?
3. Is my style okay?
4. Any ideas to speed it up or save memory?

void change(int *i, int *j)
{
int temp = *j;
 *j = *i;
*i = temp;
}


int *toplace(int *start, int *end)
{
    int *i = start+1, *j= end;

    while(i<=j)
    {
    for(; *i<=*start && i<=end; i++);
    for(; *j>=*start && start+1<=j; j--);   
    if (i<j) change(i++,j--); 
    }

    change(start,i-1); 
    return i-1;
}



void quicksort(int *start, int *end)
{
    if (start >= end) return;

    for(int *debug = start;debug<=end;debug++) std::cout<<*debug <<" ";
    std::cout<<std::endl;  //this and...

    int *temp = start;
    temp = toplace(start,end);

    for(int *debug = start;debug<=end;debug++) std::cout<<*debug <<" ";
    std::cout<<std::endl; //...this are only to "see under the hood"
    std::cout<<std::endl;

    quicksort(start,temp-1);
    quicksort(temp+1,end);

}

An example usage:

int main(int argc, char* argv[])
{
    int A[] = {5,14,8,12,1,2,11,15,6,9,7,3,13,4,10};
    int n = sizeof (A) / sizeof(A[0]);

    quicksort(A, &A[n-1]);

    for (int i =0; i<n; i++) std::cout<<A[i] <<" ";

    getchar();
    return 0;
}

produces the output:

5 14 8 12 1 2 11 15 6 9 7 3 13 4 10
1 4 3 2 5 12 11 15 6 9 7 8 13 14 10

1 4 3 2
1 4 3 2

4 3 2
2 3 4

2 3
2 3

12 11 15 6 9 7 8 13 14 10
8 11 10 6 9 7 12 13 14 15

8 11 10 6 9 7
6 7 8 10 9 11

6 7
6 7

10 9 11
9 10 11

13 14 15
13 14 15

14 15
14 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Answer 1

The interface to quicksort:

quicksort(A, &A[n-1]);

In C I would expect to see a pointer and a size.
In C++ I would expect to see two iterators (like above), but generally the end point is usually one past the end (if you want to be consistent with C++ idioms and the STL way of doing things).

quicksort(A, A+n); // This is what I would expect to see.

Change!
I would normally call this swap()

void change(int *i, int *j)
{
    int temp = *j;
     *j = *i;
     *i = temp;
}

Also in C++ I would pass the values to be swapped by reference. And there is already a std::swap() that works perfectly well.

Your for() loops that do nothing in the body.

for(; *i<=*start && i<=end; i++);

These are hard to read when doing maintenance. At first glance it looks like you accidentally did not indent the code correctly you need to study the code to understand it is correct. I find it best to put an empty body (maybe even with a comment /* Deliberately Empty */

for(; *i<=*start && i<=end; i++)  { /* Empty */ }

In your loops you are testing the loop variable against start and end. Should they not be tested against each other?

while(i<=j)
{
for(; *i<=*start && i<=end; i++);
for(; *j>=*start && start+1<=j; j--);   

// Should be:

for(; *i<=*start && i <= j; i++) { /* Empty */ }
for(; *j>=*start && i <= j; j--) { /* Empty */ }

Your quick sort seems to work but is slightly non traditional in a couple of features.

The pivot point *start. Values that are equal seem to go into both sub buckets. Traditionally they would go into a specific bucket.

You always use the first element as the pivot point. This case leads to worst case behavior of quicksort when the list is already sorted. Either choose a random element or the one in the middle of the partition.

Currently your code works with pointers to integers. But really you are using pointers as iterators. So you should templatize it so the inputs are not pointers but are generic iterators this then allows you to use the algorithm on any container type (with the side affect that it works with any type that implements the <= operator.

Answer 2

First of all there's already a std::sort function in the standard library. If you're aware of this and just wrote this as a learning exercise that's fine, but if you actually want to use this code in production, there's no reason not to use std::sort instead. That being said, here's a review of your code:

---

Efficiency

One important thing to note about your algorithm is that you're using the first element of the array as the pivot element. This is quite inefficient if you're sorting an array that is already partially sorted (leading to a quadratic runtime). You should use a random element instead.

Other than that I don't see any inefficiencies in your code.

---

Genericity

Currently your code only works on arrays of ints. This is bad because there's no reason you shouldn't be able to use a) anything that is comparable using <,> etc. instead of ints and b) other collections like for example vectors instead of arrays. If you turn your functions into template functions, you can easily achieve this simply by replacing all occurrences of int* with a template argument.

You could further generalize your sorting function by using an optional comparator argument like std::sort does.

---

Code readability and general good practices

I'd rename your change function to swap because that's what this function is usually called and the name change doesn't really give a good idea of what the function does. I'd also change it to use references instead of pointers because it's good practice to avoid using pointers if you don't need them. And again: if you didn't just re-implement this as a learning exercise, use std::swap instead of building your own (which does the same thing).

In your sort function you should rename temp to something more descriptive because the name contains absolutely no information.

Also all the print statements makes your code hard to follow. I'd remove them and use a debugger when I need to debug the code instead.

A couple of comments couldn't hurt either.