I am working on Heapsort project but i keep getting the error
Exception in thread main Java.lang.ArrayIndexOutOfBoundsException:10
at ReplacementSelection.swap(ReplacementSelection.java:42)
at ReplacementSelection.siftDown(ReplacementSelection.java:69)
at Replacement..
class ReplacementSelection {
static int[] array = new int[]{ 1,2,3,4,5,6,7,8,9,10 };
public static void sort() {
System.out.println("before:" + Arrays.toString(array));
for (int i = array.length/2; i >= 0; i--) {
siftDown(i);
}
int count = array.length-1;
while (count > 0)
{
swap(array[0], array[count]);
--count;
siftDown(0);
}
System.out.println("after:" + Arrays.toString(array));
}
public static void swap(int i, int j)
{
int tmp;
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void siftDown(int index)
{
int count = array.length;
// Left child is at index*2+1. Right child is at index*2+2;
while (true)
{
// first find the largest child
int largestChild = index*2+1;
// if left child is larger than count, then done
if (largestChild >= count)
{
break;
}
// compare with right child
if (largestChild+1 < count && array[largestChild] < array[largestChild+1])
{
++largestChild;
}
// If item is smaller than the largest child, then swap and continue.
if (array[index] < array[largestChild])
{
swap(array[index], array[largestChild]);
index = largestChild;
}
else
{
break;
}
}
}
public static void main(String[] args){
ReplacementSelection a = new ReplacementSelection();
a.sort();
}
}
You have written a swap
method which takes indices as arguments. However, you pass it the values in the array at those indices instead of the indices themselves:
swap(array[0], array[count]);
and
swap(array[index], array[largestChild]);
To fix the exception error just pass the indices to the method:
swap(0, count);
and
swap(index, largestChild);