3

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);
    }
}
Improve this question
6
  • 3
    Step 1: Use readable formatting Commented Nov 8, 2011 at 22:21
  • 1
    You will need to be more specific. What do you want your recursion to do? Commented Nov 8, 2011 at 22:22
  • 1
    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. Commented Nov 8, 2011 at 22:23
  • 3
    "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. Commented Nov 8, 2011 at 22:25
  • 1
    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. Commented Nov 8, 2011 at 22:27

8 Answers 8

Reset to default
14

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 + ", ");
        }
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Answer's description is missing.
Add description and comment to explain your answer.
@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.
Sorry bout that...I hope this helps, let me know if any more is needed.
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

}
Improve this answer

Comments

3

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;
}
Improve this answer

1 Comment

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

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] = 
}
Improve this answer

Comments

0

Try below code by providing ele as an integer array, sortedIndex=index of first element and index=index of second element: 

public static void insertionSort(int[] ele, int sortedIndex, int index) {
    if (sortedIndex < ele.length) {
        if (index < ele.length) {
            if (ele[sortedIndex] > ele[index]) {
                ele[sortedIndex] += ele[index];
                ele[index] = ele[sortedIndex] - ele[index];
                ele[sortedIndex] = ele[sortedIndex] - ele[index];
            }
            insertionSort(ele, sortedIndex, index + 1);
            return;
        }
        if (index == ele.length) {
            sortedIndex++;
        }
        insertionSort(ele, sortedIndex, sortedIndex + 1);
    }
}
Improve this answer

Comments

0 
public static void sort(int[] A, int p, int r) {
    if (p < r) {
        int q = r - 1;
        sort(A, p, q);
        combine(A, p, q, r);
    }
}

private static void combine(int[] A, int p, int q, int r) {
    int i = q - p;
    int val = A[r];
    while (i >= 0 && val < A[p + i]) {
        A[p + i + 1] = A[p + i];
        A[p + i] = val;
        i--;
    }
}

public static void main(String... strings) {
    int[] A = { 2, 5, 3, 1, 7 };
    sort(A, 0, A.length - 1);
    Arrays.stream(A).sequential().forEach(i -> System.out.print(i + ", "));
}
Improve this answer

Comments

0

Here. All the imports are to create a random array of Integers. No loops, just recursion:

import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.IntStream;
import java.util.Arrays;

public class cursedInsertSort {

  public static void sort(int[] arr) {
     if (arr == null || arr.length <= 1) {
        return;  
     }
     cursed_insertion_sort(arr, arr.length, 1);
  } 

  private static void cursed_insertion_sort(int a_list[],int len,int i) { 
     if (i >= len) return; 
     cursed_insert(a_list, i, a_list[i]); // shift and insert  
     cursed_insertion_sort(a_list, len, i + 1);  
  }
 
  private static void cursed_insert(int a_list[], int j, int val) { 
     if (j <= 0 || a_list[j-1] <= val) {  
         a_list[j] = val; // insert here 
         return; 
     } 
     a_list[j] = a_list[j-1]; // just keep shifting 
     cursed_insert(a_list, j - 1, val);  
  } 

  public static void main(String args\[\]) {
     int n = 25;
     int[] a = IntStream.range(0, n).map(i -> ThreadLocalRandom.current().nextInt()).toArray();ThreadLocalRandom.current().nextInt()).toArray();
     System.out.println("Unsorted array");
     System.out.println(Arrays.toString(a));

     sort(a);

     System.out.println("Sorted array");
     System.out.println(Arrays.toString(a));
  }
}

Output:

$ javac cursedInsertSort.java 
$ java cursedInsertSort 
Unsorted array
[1979090481, 1975907117, 1075830741, -941322152, -1787386922, -1214147410, -1064101530, -116915382, 1736910972, -1121809185, -896766788, 298102074, 659604714, 20876505, 235971615, 1779792957, 429619610, -1966855425, -617075915, -580772798, -1931560891, -982585117, -1713967857, 899010361, -1260583312]
Sorted array
[-1966855425, -1931560891, -1787386922, -1713967857, -1260583312, -1214147410, -1121809185, -1064101530, -982585117, -941322152, -896766788, -617075915, -580772798, -116915382, 20876505, 235971615, 298102074, 429619610, 659604714, 899010361, 1075830741, 1736910972, 1779792957, 1975907117, 1979090481]

``
Improve this answer

Comments

-1 
public class test
{
   public static void main(String[] args){
        test h = new test();

        int a[] = { 5, 8, 9, 13, 65, 74, 25, 44, 67, 2, 1 };

        h.ins_rec(a, a.length-1);

        for(int i=0; i<a.length; i++)
          log(a[i]);

    }



    void ins_rec(int a[], int j){
    if( j == 0 ) return;

    ins_rec(a, j - 1);
    int key = a[ j ];
    sort(a, key, j - 1);

    }



    void sort(int a[], int key, int i){
    if( (i < 0) || (a[i] < key) ) {
      a[ i + 1 ] = key;
      return;
    }

    a[ i + 1 ] = a[ i ];
    sort(a, key, i - 1);

    }



private static void log(int aMessage){
    System.out.println("\t\t"+aMessage);
  }
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.