This topic is 5206 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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)."
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);
}


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?

##### Share on other sites
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.

##### Share on other sites
After some more researching, I decided to just go for the std::sort(); algorithm but thanks anyway! :)

##### Share on other sites
Quote:
 Original post by TertsiAfter some more researching, I decided to just go for the std::sort(); algorithm but thanks anyway! :)

smart man!

##### Share on other sites
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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633726
• Total Posts
3013569
×