HiveBrain v1.2.0
Get Started
← Back to all entries
snippetcppMinor

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

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
canmadewhatbutmoreefficientquicksortfeel

Problem

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

#include 

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

        while(i  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?

Solution

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[]; // See below for more.


Pretty sure there is a bug here i 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.

Code Snippets

void quicksort(int list[], int low, int high)
//                  ^^^^^
if(low >= high)
    return;
else
int pivot = low, i = low, j = high;
int pivot = list[<location Of Pivot Value>]; // See below for more.
while(list[i] <= list[pivot] && i < high)

Context

StackExchange Code Review Q#36598, answer score: 5

Revisions (0)

No revisions yet.