Jump to content
  • Advertisement
Sign in to follow this  
Nebu

Quicksort gone wrong

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

I was using shell sort for my program and decided to move to quicksort. With shell sort my app runs fine. When I use quicksort, the app works as it should for a short none constant period of time and then crashes. When I ran it with debug I got an access violation message, ended up in this loop:
for(i=0;i<currentTri;i++)
{
   t=&triangles[indexBuffer];
   c=colBuffer[indexBuffer];
   if(!BackfaceCull(indexBuffer))
   {
	filledTrigonRGBA(screen,
		         t->v[0].x,t->v[0].y,
			 t->v[1].x,t->v[1].y,
			 t->v[2].x,t->v[2].y,
			 c->r,c->g,c->b,255);
   }
}

This is where it gets weirder, the value i should never be larger than 4500 since currentTri is 4500 at max. And on debug i was something like 3948123. I'm guessing theres some sort of corruption going on, anyway here's my quicksort code:
void Pipeline::QuickSortBuffers(int low,int high)
{
	int i,j ;

	float pivot;
	int pivot_index;

	int middle = (low+high)/2;

	pivot = zBuffer[middle];
	pivot_index = indexBuffer[middle];

	zBuffer[middle] = zBuffer[low];
	indexBuffer[middle] = indexBuffer[low];

	zBuffer[low] = pivot ;
	indexBuffer[low] = pivot_index;

	i = low;
	j = high;
	
	if (low < high)
	{
		while (i < j)
		{
			while (zBuffer[j] < pivot)
			{
				--j;
			}

			zBuffer = zBuffer[j];
			indexBuffer = indexBuffer[j];

			while (i < j && (zBuffer >= pivot))
			{
				++i;
			}

			zBuffer[j] = zBuffer;
			indexBuffer[j] = indexBuffer;
		}

		zBuffer = pivot;
		indexBuffer = pivot_index;

		QuickSortBuffers(low ,i - 1);
		QuickSortBuffers(i + 1 ,high);
	}
}

I can't figure out whats wrong with it since it does the job for a while :S. Help please :) Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Nebu
I'm guessing theres some sort of corruption going on


There is. I'm guessing, without studying it too carefully, that your code is confused about whether 'high' is supposed to index the last value in the range to be sorted, or one past that (the way that "ranges" normally behave in C++).

Quote:

I can't figure out whats wrong with it since it does the job for a while :S.
Help please :)


What's wrong with it is that you're trying to do something yourself that the standard library is already very good at. :)


// Since you're not actually using the indexes except to associate triangles
// with colors and BackfaceCull() calls and z-positions, what you really want
// to do is give the Triangle data that represents its color and z-position
// and a member function to check if it should be culled.
struct Triangle {
RGB color;
float z_position;
bool backface_cull();

Triangle(/* other args */, const RGB& color, float z_position) : /* other initialization */, color(color), z_position(z_position) { /* stuff */ }

bool operator<(const Triangle& other) { return z_position < other.z_position; }

// everything else
};

// We make a little wrapper which can "bind" a screen instance to a drawTriangle call:
struct TriangleDrawer {
SDL_Surface* screen;
TriangleDrawer(SDL_Surface* screen) : screen(screen) {}
void operator()(const Triangle& t) {
// Don't split objects up to pass a zillion parameters; pass the object
// and let the function "unpack" it. Make a separate structure to
// represent colors with an alpha component. Oh, and pass the objects
// by (const) reference, too :)
if (!t.backface_cull()) {
filledTrigonRGBA(screen, t.v, RGB(t.color, 255));
}
}
};

// Now your Pipeline can hold the actual triangles, and you sort them this easily:

void Pipeline::SortTriangles() {
std::sort(m_triangles.begin(), m_triangles.end());
}

// And you draw them this easily:
void Pipeline::DrawTriangles(SDL_Surface* screen) {
std::for_each(m_triangles.begin(), m_triangles.end(), TriangleDrawer(screen));
}


Share this post


Link to post
Share on other sites
As you can see in my function I'm sorting the array while changing another array everytime a sort action has been taken. I do this to have the correct order of triangles to draw by depth. So, having a sorted array returned wouldn't help much.

EDIT: reading above now.. to be edited once more :)

EDIT 2: I'll consider moving to std:sort but I still want to understand whats wrong with my function. I'm passing it the lowest index (0) and the highest index (currentTri-1), maybe you can review my code?

Thanks.


EDIT 3:
I took your advice and moved to std sort, but I kept my way of indexing by assigning each node 2 variables, one for depth and one for original position.
At first it was really slow and it took me a while to figure its not meant to run with debug configuration :D.
anyway it works great now,thanks for the help.

[Edited by - Nebu on June 27, 2008 11:00:30 PM]

Share this post


Link to post
Share on other sites
I have debugged your code and determined that the bug was caused by your "if (low < high)" statement being in the wrong place. It needs to be right at the start before it moves the pivot around. You don't want to go moving any items if low >= high initially!

This first off made it only approximately sort the items rather than perfectly sort them, and secondly on a recursive call where low is passed in as i+1 and i had been equal to high, and high was equal to n-1, then the line "zBuffer[middle] = zBuffer[low];" was accessing item n which is one item past the end of the array.
Moving the if statement fixes all this.

std::sort is the way to go from here!

Share this post


Link to post
Share on other sites
iMalc, THANK YOU, for your time,effort and detailed answer, that one really bugged me.

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!