Java recursive insertion sort?

Question

So I am trying to make the following code into a recursive method, insertion sort, but for as much as I try I cannot. Can anyone help me?

public static void insertionSort(int[] array){
    for (int i = 1; i < array.length; i++){
        int j = i;
        int B = array[i];
        while ((j > 0) && (array[j-1] > B)){
            array[j] = array[j-1];
            j--;
        }
        array[j] = B;
    }
}

EDIT: I was thinking of something like this, but it doesn't look very recursive to me...

public static void insertionSort(int[] array, int index){
    if(index < array.length){
        int j = index;
        int B = array[index];
        while ((j > 0) && (array[j-1] > B)){
            array[j] = array[j-1];
            j--;
        }
        array[j] = B;
        insertionSort(array, index + 1);
    }
}

Solution 1

Try this:

public class RecursiveInsertionSort {
    static int[] arr = {5, 2, 4, 6, 1, 3};
    int maxIndex = arr.length;

    public static void main(String[] args) {
        print(arr);
        new RecursiveInsertionSort().sort(arr.length);
    }

    /*
      The sorting function uses 'index' instead of 'copying the array' in each    
      recursive call to conserve memory and improve efficiency.
    */
    private int sort(int maxIndex) {
        if (maxIndex <= 1) {
            // at this point maxIndex points to the second element in the array.
            return maxIndex;
        }

        maxIndex = sort(maxIndex - 1);  // recursive call

        // save a copy of the value in variable 'key'.
        // This value will be placed in the correct position
        // after the while loop below ends.
        int key = arr[maxIndex];  

        int i = maxIndex - 1;

        // compare value in 'key' with all the elements in array 
        // that come before the element key. 
        while ((i >= 0) && (arr[i] > key)) {
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = key;
        print(arr);
        return maxIndex + 1;
    }

    // code to print the array on the console.
    private static void print(int[] arr) {
        System.out.println();
        for (int i : arr) {
            System.out.print(i + ", ");
        }
    }
}

Solution 2

You can try this code. It works correctly.

public static int[] InsertionSort(int[] dizi, int n) 
{
    int i;
    if (n < 1) {
        InsertionSort(dizi, n - 1);
    } 
    else {

        int key = dizi[n];
        i = n - 1;

        while (i >= 0 && dizi[i] > key) {
            dizi[i + 1] = dizi[i];
            i = i - 1;
        }

        dizi[i + 1] = key;
    }

    return dizi;
}

Solution 3

public static void insertionSort(int[] array, int index) {
    if(array.length == index + 1) return;

    insertionSort(array, index + 1);

    // insert array[index] into the array

}

Solution 4

for the recursion algorithm, we start with the whole array A[1..n], we sort A[1..n-1] and then insert A[n] into the correct position.

public int[] insertionSort(int[] array)
{
   //base case
   if(array.length==1) return new int[]{ array[0] };

   //get array[0..n-1] and sort it
   int[] arrayToSort = new int[array.length - 1]{ };
   System.arraycopy(array, 0, arrayToSort, 0, array.length -1);
   int[] B = insertionSort(arrayToSort);

   //now, insert array[n] into its correct position
   int[] C = merge(B, array[array.length - 1]);

   return C;
}

private int[] merge(int[] array, int n)
{ 
   int[] arrayToReturn = new int[array.length + 1] {};
   int j = array.length-1;
   while(j>=0 && n <= array[j])
   {
      arrayToReturn[j+1]=array[j;
      j--;
   }

   arrayToReturn[j] = 
}

View more solutions

Comments

[Admin]

Step 1: Use readable formatting

[Oliver Charlesworth]

You will need to be more specific. What do you want your recursion to do?

[Ren]

I want the method to be recursive. To call itself inside of the method and then have a base condition that would stop it from calling itself forever.

[phwd]

"for as much as I try I cannot" <- Could you edit your question to show the methods you have tried even if it is pseudocode.

[Ren]

Well, I was thinking of taking the for loop out, and instead making it recursive by calling the method again with different data inside, but I get confused when I try to do it.

[phwd]

You still have not edited the question.**Please edit and place all the information in there.** Actually describing how far you tried is better than us just giving you a recursive sort at not effort to you.

[Mayur Birari]

Answer's description is missing.

[0xC0DED00D]

Add description and comment to explain your answer.

[akjoshi]

@Varun: Welcome to SO, try and add some explanation to your answers, having some comments in the code will also be helpful for others in understanding/improve it quickly.

[Varun Verma]

Sorry bout that...I hope this helps, let me know if any more is needed.

[James H]

It does not actually work correctly. And when you answer, best to answer with explanations.