Public Group

#### Archived

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

# index bounding error

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

## 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 on other sites
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 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 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

1. 1
2. 2
Rutin
20
3. 3
4. 4
A4L
15
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633737
• Total Posts
3013614
×