Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Kelendil

Quicksort problem

This topic is 5386 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

void sortFast( std::vector<Data> &v, int leftLimit, int rightLimit )
{
	int pivot = leftLimit;
	int i = leftLimit + 1;
	int j = rightLimit;
	int temp;
	if ((rightLimit - leftLimit) >= 1)
	{
		while (j >= i)
		{
			while (v[i].number <= v[pivot].number && i < rightLimit)
				i++;


			while (v[j].number >= v[pivot].number && j > pivot)
				j--;



			if (i < j)
			{
				temp = v[i].number;
				v[i].number = v[j].number;
				v[j].number = temp;
			}
			else
			{
				temp = v[j].number;
				v[j].number = v[pivot].number;
				v[pivot].number = temp;
			}
		}
		
		sortFast( v, leftLimit, (j - 1) );
		sortFast( v, (j + 1), rightLimit );
	}	
}
Can someone tell me what's wrong with this quicksort algorithm? There is a slight amount of data that doesn't get sorted. [edited by - kelendil on September 23, 2003 10:25:03 PM]

Share this post


Link to post
Share on other sites
Advertisement
Hmm... I don''t sort the element at ''j'' because it is already sorted. All data to the left of it is smaller and all data to the right of it is greater.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

if (i < j)
{
temp = v[i].number;
v[i].number = v[j].number;
v[j].number = temp;
}
else
{
temp = v[j].number;
v[j].number = v[pivot].number;
v[pivot].number = temp;
}


That part, along with other possible off-by-one errors, is wrong. You just want to swap the number field for v and v[j] at this point. You don''t want to change the value at the pivot index. Remember, the partition portion of this algorithm just moves values less than the value at the pivot index (v[pivot].number) to the left of the pivot index and values greater than the value at the pivot index to the right of the pivot index. It doesn''t impose any order on the values that are placed to the left or right. The partition algorithm only imposes the following rule:

n_i <= n_p for all i < p and n_j >= n_p for all j > p

This means the value at the pth index is sorted, although the rest of the array may not be. Recursion then takes over as sort(0, p-1) and sort(p+1, MAX) are called.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!