Sign in to follow this  

question about quicksort

This topic is 4838 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[left];
	while (left < right)
	{
		while ((array[right] >= pivot) && (left < right)) --right;
		if (left != right)
		{
			array[left] = numbers[right];
			++left;
		}
		while ((array[left] <= pivot) && (left < right)) ++left;
		if (left != right)
		{
			array[right] = array[left];
			--right;
		}
	}
	array[left] = 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
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

This topic is 4838 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this