# I feel as if my quicksort can be made more efficient, but what?

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 = { 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?

• Is this just C++? The only C here are some of the libraries.
– Jamal
Dec 3, 2013 at 19:18
• @Jamal Yea, sorry, I had used the C libs to sleep for debugging purposes. Dec 3, 2013 at 19:19

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.

• Why is i < high and j > low not correct? (This implementation works) Dec 4, 2013 at 3:07
• 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. Dec 4, 2013 at 4:42

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!

• std::swap(list[i], list[j]); would make it even neater.
– Jamal
Dec 3, 2013 at 20:12
• 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.