Jump to content
  • Advertisement

Archived

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

vaneger

index bounding error

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

template<class type>
void quicksort(apvector<type> &a, int l, int r)
{
	mDepth++;
    if (l >= r) return;
    int i, j;
    int num_left, num_right;
    type pivot, temp;

    while (l < r)
    {
        i = l;
        j = r + 1;
        pivot = a[l];
        while (true)
        {
            do
            {
              i = i + 1;
            }
            while (a[i] < pivot);
            
            do
            {
                j = j - 1;
            }
            while (a[j] > pivot);
            
            if (i >= j) break;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        };
        
        a[l] = a[j];
        a[j] = pivot;
        
        num_left  = (j-1) - l;
        num_right = r - (j+1);
        
        if (num_left <= num_right)
        {
            quicksort(a, l, j-1);
            l = j+1;
        }
        else
        {
            quicksort(a, j+1, r);
            r = j-1;
        }
    }
}
for some reason my quick sort randomly goes out of bounds and im not sure where it goes out of bounds or why.

Share this post


Link to post
Share on other sites
Advertisement
1: No wonder you''re having difficulty tracking errors with such terrible variable names. Call them something to do with what they''re actually for. This isn''t a graphics calculator - you aren''t limited to the 26 letters of the alphabet.
2: Uh... do you know that there''s a quicksort in the C standard library?

Share this post


Link to post
Share on other sites
You know you could just trace it over using a debugger. Should be able to find the line going out of bound pretty easily.





--{You fight like a dairy farmer!}

Share this post


Link to post
Share on other sites
Heya vaneger,

I copied your source and wrote a quick test program...I tested it sorting about 100 numbers about 1000 times, and it never crashed on me.

The only differences I made were commenting out mDepth++, and I changed your apvector into a "long *a", so that I''d be working with an array of longs. Then I removed all references to type and replaced it with "long".

The things to look at now are your initial inputs to quicksort, make sure they are valid indices into your array. Also, since I dont have your code for "type" I''m not sure how you''re comparing those data types. You might check to make sure your comparison operators are correct for you template classes.

Best Regards,
Jeromy Walsh
Programmer
Liquid Entertainment

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!