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

Question

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?

Answer 1

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.

Answer 2

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!

Answer 3

• 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.