15
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I don't see any pointer issues. Nice work! \$\endgroup\$ – Hunter McMillen Nov 24 '11 at 16:06
  • \$\begingroup\$ Or you have wrong copy-paste or 2nd test from the top is failed. \$\endgroup\$ – Hauleth Nov 24 '11 at 16:10
  • 1
    \$\begingroup\$ @Caleb - me too. Except I could not find that site on the list which appeared, so I just flagged it as offtopic. Can you somehow get it on that list? \$\endgroup\$ – Vilx- Nov 24 '11 at 16:10
  • \$\begingroup\$ @Vilx, when you flag you can use the 'needs moderator attention' option and type a comment in the box suggesting migration to a different site. \$\endgroup\$ – Caleb Nov 24 '11 at 16:27
  • 2
    \$\begingroup\$ Not really C++ is it! \$\endgroup\$ – Martin York Nov 24 '11 at 17:15
10
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'd refactor these for loops to while(*i<=*start && i<=end) i++; and while(*j>=*start && start+1<=j) j--; \$\endgroup\$ – user7871 Nov 25 '11 at 2:04
  • \$\begingroup\$ Thank you @Loki Astari! Really appreciated. That was what I expected. \$\endgroup\$ – Kolt Nov 25 '11 at 9:20
10
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you! I will take a look on std::sort(). I actually created this to learn c++. I already new the algorithm from school (class: algorithm design and analysis). Now I changed using the first element as pivot element to use the one in the middle. Thank you for good comment. \$\endgroup\$ – Kolt Nov 25 '11 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.