Quicksort gone wrong

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

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 on other sites
Since it looks like you're using C++, why not just use std::sort()?

Share on other sites
Quote:
 Original post by NebuI'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 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 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 on other sites
iMalc, THANK YOU, for your time,effort and detailed answer, that one really bugged me.

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 11
• 10
• 13
• 96
• 11
• Forum Statistics

• Total Topics
632974
• Total Posts
3009643
• Who's Online (See full list)

There are no registered users currently online

×