Is this C++ quicksort program okay?

I wrote a quicksort program in C++.

• Is it okay to implement it this way?

• Am I using pointers correctly?

• Is my style okay?

• 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=*start && start+1= 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

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=*start && start+1=*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.

StackExchange Code Review Q#6257, answer score: 10