Jump to content
  • Advertisement

Archived

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

Kelendil

Quicksort problem

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

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!