Recursive Selection Sort Stack Overflow Error

Question

import java.util.Arrays;

public class RecSelect {

    public static void Select(int[] ar, int idx, int min, int start) {
        if(idx == ar.length) {
            return;
        }
        if(idx < ar.length - start) {
            if(ar[min] > ar[idx]) {
            min = idx;
            Select(ar, idx+1, min,0);
            }
            else {
            Select(ar, idx+1, min,0);
            }
            int temp = ar[min];
            ar[min] = ar[start];
            ar[start] = temp;

        Select(ar, start + 2, start + 1, start + 1);
        }
    }

    public static void main(String[] args) {
        int[] ar = {5, 3, 1, 8, 2};
        Select(ar, 1, 0, 0);
        System.out.println(Arrays.toString(ar));
    }
}

Please guide me, why is this giving stack overflow error, although I have used a base condition.

Tell me what must be corrected.

There are another methods using for loop and one with creating a findMin() function. But I want to do it this way. HELP!

Answer 1

Here are the issues:

• The recursive call Select(ar, idx+1, min,0); -- that is intended to find the minimum in the unsorted part of the array -- passes 0 as the value for start, but that ignores the value for start that you got, and which indicates the first index of the unsorted part of the array. As most of the remaining logic for sorting the array happens deeper in recursion, you're actually throwing away the achievements you already made, and start sorting from index 0 onwards again. This leads to infinite recursion.

• When unwinding from the above mentioned recursion, you swap the value at min with the value at start. But because there are multiple recursive calls that were made to find the minimum, this swap will happen multiple times. Moreover, as min is a local variable, it will happen with wrong values for min as well. You should only make one swap per scan through the unsorted array, and it should only happen when you have the final value for min. To achieve both those targets, put this swap code in the if block where idx has reached the end of the array.

• You have another recursive call at the end of the function body: Select(ar, start + 2, start + 1, start + 1). This is intended to grow the sorted part of the array with one unit, and repeat the selection procedure for the next element. But similar to the above problem, this should only execute once for each start. But because you had several levels of recursion with the first type of recursive call, you'll also have multiple calls of the second type of recursive call. This will lead to an exponential number of calls that are no longer necessary, as after one such call has completely finished, the array is already sorted. To fix this, make sure that you first unwind from the first type of recursive call until you are back where idx is one more than start. Only then make the second type of recursive call.

• The condition if(idx < ar.length - start) has nothing to do with selection sort. It makes me think of some bubblesort logic, but here it makes no sense. Even when start is non-zero, you still need idx to walk all the way to the end to find the minimum. So remove this if wrapper.

Here is the corrected code for Select:

    public static void Select(int[] ar, int idx, int min, int start) {
        if (idx >= ar.length) {
            // swap only once for a given start, so do that here
            int temp = ar[min];
            ar[min] = ar[start];
            ar[start] = temp;
            return;
        }
        if (ar[min] > ar[idx]) {
            min = idx;
        }
        Select(ar, idx+1, min, start); // last argument must be start, not 0
        if (idx > start + 1) {
            return; // unwind before performing the below recursive call
        }        
        Select(ar, start + 2, start + 1, start + 1);
    }