javasortingheapsort

Heapsort ArrayIndexOutOfBoundsException


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();
    }
}

Solution

  • 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);