Bug in recursive selection sort?

Question

I am trying to implement selection sort recursively in java, but my program keeps throwing an ArrayIndexOutOfBounds exception. Not sure what I am doing wrong. Recursion is very hard for me. Please help! I am a beginner.

public static int[] selection(int[] array) {
    return sRec(array, array.length - 1, 0);
}
private static int[] sRec(int[] array, int length, int current) {
    if (length == current) { //last index of array = index we are at
        return array; //it's sorted
    }
    else {
            int index = findBig(array, length, current, 0);
            int[] swapped = swap(array, index, length - current);
            return sRec(swapped, length - 1, current);
    }
}

private static int[] swap(int[] array, int index, int lastPos) {
    int temp = array[lastPos];
    array[lastPos] = array[index];
    array[index] = array[temp];
    return array;
}

private static int findBig(int[] array, int length, int current, int biggestIndex) {
    if (length  == current) {
        return biggestIndex;
    }
    else if (array[biggestIndex] < array[current]) {
        return findBig(array, length, current + 1, current);
    }
    else {
        return findBig(array, length, current + 1, biggestIndex);
    }
}

public static void main (String [] args) {
    int[] array = {8,3,5,1,3};
    int[] sorted = selection(array);
    for (int i = 0; i < sorted.length; i++) {
        System.out.print(sorted[i] + " ");
    }
}

Answer 1

I tested your code and it did not sort even after having fixed the "Out Of bound Exception". I've changed your method findBig in order to make it work. The principle is :

1. If the length of the sub array is one (begin==end) then the biggest element is array[begin]
2. divide the array by half
3. Recusively find the index of the biggest element in the left side
4. Recursively find the index if the biggest element in the right side
5. Compare the biggest element of the left side with that of the right side of the array and return the index of the biggest of both.

This leads to the following code which sort the array in a decreasing order:

public class Sort {

   public static int[] selection(int[] array) {
        return sRec(array,0);
    }
    private static int[] sRec(int[] array, int current) {
      if (current == array.length-1) { //last index of array = index we are at
            return array; //it's sorted
        }
        else {
                int indexOfBiggest = findBig(array, current,array.length-1);
                int[] swapped = swap(array, indexOfBiggest, current );
                return sRec(swapped, current+1);
        }
    }

    private static int[] swap(int[] array, int index, int lastPos) {
        int temp = array[lastPos];
        array[lastPos] = array[index];
        array[index] = temp;
        return array;
    }

    private static int findBig(int[] array, int begin, int end) {
        if (begin < end) {
            int middle = (begin+end)/2;
            int biggestLeft = findBig(array,begin,middle);
            int biggestRight = findBig(array,middle+1,end);
            if(array[biggestLeft] > array[biggestRight]) {
                return biggestLeft;
            }else {
                return biggestRight;
            }
        }else {
            return begin;
        }
     }

    public static void main (String [] args) {
        int[] array = {8,3,5,1,3};
       // System.out.println(findBig(array,0,array.length-1));
        int[] sorted = selection(array);
        for (int i = 0; i < sorted.length; i++) {
            System.out.print(sorted[i] + " ");
        }
    }
}