snippetcppMinor
I feel as if my quicksort can be made more efficient, but what?
Viewed 0 times
canmadewhatbutmoreefficientquicksortfeel
Problem
I just learned the quicksort algorithm and tried to implement it, but it feels dirty:
The
What can I improve?
#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.
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
It looks neater and saves you a level of indentation.
One variable per line.
Also give the variables more meaningful names.
Also I would say that pivot is really the value you are pivoting around. Not the location of the value you are pivoting around.
Pretty sure there is a bug here
Yep. You are correct the break is ugly here.
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?
You pass the location of the first and last element in the array.
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.
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;
elseIt 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;
elseint 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.