3
\$\begingroup\$

I just learned the quicksort algorithm and tried to implement it, but it feels dirty:

#include <iostream>

void quicksort(int list[], int low, int high)
{   
    if(low >= high)
        return;
    else
    {
        int pivot = low, i = low, j = high;

        while(i < j)
        {
            while(list[i] <= list[pivot] && i < high)
            {
                i++;
            }

            while(list[j] > list[pivot] && j > low)
            {
                j--;
            }

            if(i > j)
                break;

            int temp = list[i];
            list[i] = list[j];
            list[j] = temp;
        }

        int temp = list[pivot];
        list[pivot] = list[j];
        list[j] = temp;

        quicksort(list, low, j-1);
        quicksort(list, j+1, high);

    }
}

int main()
{
    int arr[10] = { 12, 2, 24, 32, 5, 1203, 7, 123, 2354, 2 };
    quicksort(arr, 0, 9);

    for(int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
}

The break condition in the while loop feels really cheap; as if I did something wrong and needed to put it there...

What can I improve?

\$\endgroup\$
  • \$\begingroup\$ Is this just C++? The only C here are some of the libraries. \$\endgroup\$ – Jamal Dec 3 '13 at 19:18
  • \$\begingroup\$ @Jamal Yea, sorry, I had used the C libs to sleep for debugging purposes. \$\endgroup\$ – Kenneth Worden Dec 3 '13 at 19:19
5
\$\begingroup\$

I don't like seeing arrays passed as parameters.

void quicksort(int list[], int low, int high)
//                  ^^^^^

Inside the function all similarity to an array has disappeared. It has decayed into a pointer. By using the array like syntax you might catch people out that want to treat it as an array (which is a real maintenance issue).

If this code is C then just pass as a pointer.
If this code is C++ then pass as a reference to an array, or use a container type and pass by reference (I prefer the container option as you can template it).

In quick pre-condition checks at the head of a function like this.
There is no need for the else part.

if(low >= high)
    return;
else

It looks neater and saves you a level of indentation.

One variable per line.
Also give the variables more meaningful names.

    int pivot = low, i = low, j = high;

Also I would say that pivot is really the value you are pivoting around. Not the location of the value you are pivoting around.

    int pivot = list[<location Of Pivot Value>]; // See below for more.

Pretty sure there is a bug here i < high is not correct.

        while(list[i] <= list[pivot] && i < high)

Same thing here. Pretty sure there is a bug here j > low is not correct.

        while(list[j] > list[pivot] && j > low)

Yep. You are correct the break is ugly here.

        if(i < j)
        {    std::swap(list[i], list[j]);
        }

You are only doing this (below) to prevent your self choosing the same pivot point each time. So you should choose a different technique to choose the pivot point. Why not the element in the middle of the list?

    int temp = list[pivot];
    list[pivot] = list[j];
    list[j] = temp;

You pass the location of the first and last element in the array.

    quicksort(list, low, j-1);
    quicksort(list, j+1, high);

It is more C++ like to use first and one past the point you consider end. It also makes the code look neater try it and see.

\$\endgroup\$
  • \$\begingroup\$ Why is i < high and j > low not correct? (This implementation works) \$\endgroup\$ – Kenneth Worden Dec 4 '13 at 3:07
  • \$\begingroup\$ If its not the first time through the outer loop. Then i could blow past j all the way to high. Even if works it does not make logical sense. \$\endgroup\$ – Martin York Dec 4 '13 at 4:42
3
\$\begingroup\$

There are three things I can see which can improve (but this is a far from complete answer... there may be more)..

  1. You can start i at low + 1, which will save you a comparison on each pivot.
  2. Your i loop should be terminated at i < j and not i < high.
  3. Your j loop should be terminated at j > i and not j > low.

This should save a bunch of comparisons.....

if the break; looks wrong to you, then you should just reverse the logic:

    if(j > i) {
        std::swap(list[i], list[j]);
    }

There, much neater!

\$\endgroup\$
  • 1
    \$\begingroup\$ std::swap(list[i], list[j]); would make it even neater. \$\endgroup\$ – Jamal Dec 3 '13 at 20:12
2
\$\begingroup\$
  • Prefer std::size_t for the loop. This is especially helpful if an int is not large enough.

  • Prefer to let the compiler determine the array size. It'll also prevent errors if you add/remove elements without changing the size.

    int arr[] = { 12, 2, 24, 32, 5, 1203, 7, 123, 2354, 2 };
    

    Similar issue here:

    quicksort(arr, 0, 9);
    

    If you modify your array size without updating the third parameter, you'll run into problems.

    If you don't want to bother with this, I'd recommend an STL container such as std::vector. With that, you can do this:

    std::vector<int> origVec = { 12, 2, 24, 32, 5, 1203, 7, 123, 2354, 2 };
    
    std::vector<int> sortedVec = quicksort(origVec);
    
    // parameters in definition
    std::vector<int> quicksort(std::vector<int> const& origVec) { }
    

    In your function, vec.front() would be your low and vec.back() would be your high. These return values adjust to your vector contents, so you won't have to keep track of size.

\$\endgroup\$

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.