void quicksort(int array[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers;
while (left < right)
{
while ((array >= pivot) && (left < right)) --right;
if (left != right)
{
array = numbers;
++left;
}
while ((array <= pivot) && (left < right)) ++left;
if (left != right)
{
array = array;
--right;
}
}
array = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if(left < pivot) quicksort(array, left, pivot-1);
if(right > pivot) quicksort(array, pivot+1, right);
}
question about quicksort
Author
Here's an excerpt from http://linux.wku.edu/~lamonml/algor/sort/quick.html:
"The efficiency of the algorithm is majorly impacted by which element is choosen as the pivot point. The worst-case efficiency of the quick sort, O(n2), occurs when the list is sorted and the left-most element is chosen. Randomly choosing a pivot point rather than using the left-most element is recommended if the data to be sorted isn't random. As long as the pivot point is chosen randomly, the quick sort has an algorithmic complexity of O(n log n)."
So which ones of those pivot = left; statements would it be recommended to replace with:
pivot = numbers[XIRandom(left,right)];
if the data to be sorted isn't random?
Just use the middle element as a pivot. If list is sort it'll turn worst-case scenario to best-case scenario.
And if the list is random then the middle element is equally good choice as choosing the left most or a random element.
And if the list is random then the middle element is equally good choice as choosing the left most or a random element.
Author
After some more researching, I decided to just go for the std::sort(); algorithm but thanks anyway! :)
Quote:Original post by Tertsi
After some more researching, I decided to just go for the std::sort(); algorithm but thanks anyway! :)
smart man!
If you want something simpler than Quicksort with good performance use a merge sort. Although you're using STD::Sort() now, you may run into some situation where that might not work.
Also, to ensure better performance, look into Hoare and Lomuto (spelt totally wrong) derivations of quicksort. They both have solid pivot checking. Even if you just preview some of the list first you will not decrease the efficeicncy the big O efficency by a factor of N, simply a constant.
Also, to ensure better performance, look into Hoare and Lomuto (spelt totally wrong) derivations of quicksort. They both have solid pivot checking. Even if you just preview some of the list first you will not decrease the efficeicncy the big O efficency by a factor of N, simply a constant.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
