Cannot convert insertion sort to recursively

user_14485433 0
Viewed 38
public static void insertionSort(int[] a) {
    for(int i = 1; i < a.length; i++) {
        int minVal = a[i];
        int checkIdx = i-1;
        
        while(checkIdx >= 0 && minVal < a[checkIdx]) {
            a[checkIdx + 1] = a[checkIdx];
            checkIdx--;
        }
        
        a[checkIdx + 1] = minVal;
    }
}

This is my solution for insertion sort iteratively, but what I want is to transform this code recursively. I tried but I got stuck myself in one part.

public static void insertionSort(int[] arr, int i, int n)
{
    int value = arr[i];
    int j = i;

    // Find index j within the sorted subset arr[0..i-1]
    // where element arr[i] belongs
    while (j > 0 && arr[j - 1] > value)
    {
        arr[j] = arr[j - 1];
        j--;
    }

    arr[j] = value;

    // Note that subarray arr[j..i-1] is shifted to
    // the right by one position i.e. arr[j+1..i]

    if (i + 1 <= n) {
        insertionSort(arr, i + 1, n);
    }
}

I got stuck myself in the while loop part, how can I convert it to recursively??

recursion java
2 Answers

You are almost there. Only one thing. You need to break out of recursion at some point. That will be the condition when the array is sorted and i+1 == n. Very slightly edited code. The original array is {4,2,7,8,1,9,3,5,6,0} which is finally sorted.

public class insertionSort_Edited {
    public static int[] insertionSort (int[] arr, int i, int n){
        int value = arr[i];
        int j = i;

        // Find index j within the sorted subset arr[0..i-1]
        // where element arr[i] belongs
        while (j > 0 && arr[j - 1] > value)
        {
            arr[j] = arr[j - 1];
            j--;
        }

        arr[j] = value;

        // Note that subarray arr[j..i-1] is shifted to
        // the right by one position i.e. arr[j+1..i]

        if (i + 1 < n ) {
            insertionSort(arr, i + 1, n);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] MyArray= new int[]{4,2,7,8,1,9,3,5,6,0};
        MyArray = insertionSort(MyArray, 0, 10);
        for(int i=0;i<MyArray.length;i++){
            System.out.println(MyArray[i]);
        }
    }
}

Gives the following output.

0
1
2
3
4
5
6
7
8
9
user_74804600

Ok so I have solved it, thx for helping me.

public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

public static void check(int[] array, int i) {
    if (i == 0) {
        return;
    } 
    if (array[i] >= array[i - 1]) {
        return;
    } 
    swap(array, i, i - 1);
    check(array, i - 1);
}

public static void recurInsertionSort(int[] a, int minPos, int last) {
    check(a,minPos);
    
    if(minPos + 1 <= last) {
        recurInsertionSort(a,minPos + 1, last);
    }
    
}
user_144854330
Related