ArrayIndexOutOfBounds error!!!help

[sh33p1985]

i have the following couting sort algorithm, but i get an array index out of bounds error and i cant find my mistake!

public static double sort(int array[], int n){
double startTime = System.currentTimeMillis();
int b[];
b = new int[n];
int c[];
c = new int[n];

for(int i = 0; i < n; i++){
c[i] = 0;
}

for(int j = 0; j < array.length; j++){
c[array[j]] = c[array[j]] + 1;
}
for(int k = 1; k < n; k++){
c[k] = c[k] + c[k - 1];
}
for(int l = array.length - 1; l >= 0; l--){
b[c[array[l]]] = array[l];
c[array[l]] = c[array[l]] - 1;
}
}

[Kram]

i dont suppose the error tells you which array is out of bounds? I dont think it does, what you can do to find out which array has the problem is to simply cut out one of the for loops you have and see if the error goes away. Then once you have isolated the error you need to sit down with i cup of coffee and look long and hard at the values of all of the variables you are using

also could you give an example of values being passed into the function so we can work with something?

[ractoc]

I think the problem lies in your second for loop. Here you loop through array[] and put the value you get from the array as index on the c[]. This goes ok as long as that value is smaller than the size of the c[], but when you get a value that's bigger then the size of c[] (array[i] >= n) you will get an arrayIndexOutOfBounds exception.

On a side note, why don't you just convert the entire array[] to a collection Object? These already have built in sorting methods... After you have sorted the collection, you can convert back to an array and voila...

[sh33p1985]

still not having much luck fixing it!well, its a coursework, comparing the runtimes of 2 algorithms that we've learnt, a simple one, insertions and a more complex one, chose counting...so have to try and get it working this way im afraid, ill keep pluggin away at it today see if i can sort it, suggestions still welcome!

[sh33p1985]

countingsort(A[], B[], k)
for i = 1 to k do
C[i] = 0

for j = 1 to length(A) do
C[A[j]] = C[A[j]] + 1

for 2 = 1 to k do
C[i] = C[i] + C[i-1]

for j = 1 to length(A) do
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1

thats the psuedocode i worked off

[ractoc]

Could you attach the complete .java file? so I can see how you are calling the sort method?

[sh33p1985]

Originally posted by ractoc
Could you attach the complete .java file? so I can see how you are calling the sort method?

public static double sort(int array[], int n){

double startTime = System.currentTimeMillis();
int b[];
b = new int[n];
int c[];
c = new int[n + 1];

for(int i = 0; i < n; i++){
b[i] = 0;
}
for(int i = 0; i < n + 1; i++){
c[i] = 0;
}

for(int j = 0; j < array.length; j++){
c[array[j]] = c[array[j]] + 1;

}

for(int k = 1; k < n; k++){
c[k] = c[k] + c[k - 1];
}

for(int j = array.length - 1; j >= 0; j--){
b[c[array[j]]] = array[j];
c[array[j] + 1] = c[array[j]] - 1;
}

double finishTime = System.currentTimeMillis();
double runTime = finishTime - startTime;

String outputFile = "averageCaseCountingOutput.txt";
try{
FileWriter fw = new FileWriter(outputFile);
PrintWriter pw = new PrintWriter(fw);
int z;
for(int i = 0; i < b.length; i++){
z = b[i]; pw.println(z);
}
pw.close();
}
catch(Exception e){
System.out.println(e);
}
finally{
}
return(runTime);

}

[ractoc]

and you call this method with an int[] and ==int[].length?

Because, as stated before, with the current code n must be at least 1 higher than the highest value in the array.

[sh33p1985]

Originally posted by ractoc
and you call this method with an int[] and ==int[].length?

Because, as stated before, with the current code n must be at least 1 higher than the highest value in the array.

i call it with:

sort(array, n);

where array is the array to be sorted and n is the size of the array, e.g 100 (indexed 0 to 99) of random numbers between 0 and 100.

[ractoc]

hhmmzz.. I'll have to look into this more carefully then...
Which I can't do right noe, since I'm at work and all...

[sh33p1985]

cheers mate, much appreciated

[sh33p1985]

well i just spent an HOUR testing it using a hardcoded array, outputting all the arrays after each loop to check if each section was working, the problem wa sin the last loop....

for(int j = array.length - 1; j >= 0; j--){
b[c[array[j]] - 1] = array[j];
c[array[j]] = c[array[j]] - 1;
}

originially it was b[c[array[j]]] which meant it was trying to put the largest number in the array into b[5] which doesnt exist obviously!
i wish theyd do psuedocode like how java indexes arrays!:P

[ractoc]

Java arrays are 0 delimited, so an array of size 5 will have the following indexes:
0,1,2,3,4