Jump to content
  • Advertisement
Sign in to follow this  
Tertsi

question about quicksort

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


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

smart man!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!