Recursive Insertion Sort

user_13118075 0
Viewed 433

I have the following problem that I'm having trouble with, particularly in some of the parts where some of the code is given to me.

Problem Description: Given an array of integers, return an array containing the same integers sorted from the largest to the smallest using insertion sort. We'll use the convention of considering only part of the array that begins at a given index and ends at another. In this way, a recursive call can work through any part of the array. The initial call will pass in index 0 and the index to the last element.

insertionSort([2, 1, 3, -2, 8], 0, 4) → [8, 3, 2, 1, -2]
insertionSort([2, 6, -4], 0, 2) → [6, 2, -4]
insertionSort([2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22], 0, 10) → [22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2]

Code Given:

public int[] insertionSort(int[] nums, int begin, int end) {

}

void insert(int[] nums, int begin, int end, int element) {
  int index=end;
  while(index>=begin && nums[index]<element) {
    index--;
  }
  for(int i=end; i>index; i--) {
    nums[i+1] = nums[i];
  }
  nums[index+1] = element;
}

What I'm having trouble with is understanding what the "element" variable means in the "insert" method.

Here is the code I have written for it.

public int[] insertionSort(int[] nums, int begin, int end) {
 if(begin >= end) return nums;
 else if (begin < end){

   int element = nums.length;
   insert(nums, begin, end, element);
   insertionSort(nums, begin, end);

  }
  return nums;
}

void insert(int[] nums, int begin, int end, int element) {
  int index=end;
  while(index>=begin && nums[index]<element) {
    index--;
  }
  for(int i=end; i>index; i--) {
    nums[i+1] = nums[i];
  }
  nums[index+1] = element;
}

This are the errors I get from my code:

enter image description here

insertion-sort java
4 Answers

so what you are doing wrong is passing the element as nums.length, element is the number to be inserted, that is after each recursive call it would be (begin+1)th element, and you will keep increasing begin by 1 as that part of array(0 to begin) would be already sorted. SO the next time insertionsort would be called on begin+1 to end. Here is the working sample below. 

public class Main
{

    public static int[] insertionSort(int[] nums, int begin, int end) {
 if(begin >= end) return nums;
 else if (begin < end){

   int element = nums[begin+1];
   insert(nums, 0, begin, element);
   insertionSort(nums, begin+1, end);

  }
  return nums;
}

static void  insert(int[] nums, int begin, int end, int element) {
  int index=end;
  while(index>=begin && nums[index]<element) {
    index--;
  }
  for(int i=end; i>index; i--) {
    nums[i+1] = nums[i];
  }
  nums[index+1] = element;
}

    public static void main(String[] args) {
        int[] a = {3,41,0,10};
        int[] t = insertionSort(a, 0, 3);
        for (int i =0; i<4; i++){
            System.out.println(t[i]);
        }
    }
}
user_74194570

I think this is more or less what you are trying to do.

class RecursiveInsertionSort {

    public static void main(String[ ] args) {
        int[] input1 = {2, 1, 3, -2, 8};
        int[] input2 = {2, 6, -4};
        int[] input3 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22};

        int[] res1 = insertionSort(input1, 0, 4);
        // res1 = [8, 3, 2, 1, -2]

        int[] res2 = insertionSort(input2, 0, 2);
        // res2 = [6, 2, -4]

        int[] res3 = insertionSort(input3, 0, 10);
        // res3 = [22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2]
    }

    public static int[] insertionSort(int[] nums, int begin, int end) {
        if(begin >= end) {
            return nums; // We are done
        }

        // Sort the first n-1 elements
        insertionSort(nums, begin, end - 1);

        // Insert the nth element in the first n-1 elements array
        insert(nums, begin, end - 1, nums[end]);

        return nums;
    }

    static void insert(int[] nums, int begin, int end, int element) {
        int index = end;
        while(index >= begin && nums[index] < element) {
            index--;
        }
        for(int i = end; i > index; i--) {
            nums[i + 1] = nums[i];
        }
        nums[index + 1] = element;
    }
}
user_10312960

Non recursive version:

    public static int[] insertionSort(int[] nums, int begin, int end) {

        for (int i = begin + 1; i <= end; i++) {
            insert(nums, begin, i - 1, nums[i]);
        }

        return nums;
    }

    public static void insert(int[] nums, int begin, int end, int element) {
        int index=end;
        while(index>=begin && nums[index]<element) {
            index--;
        }
        for(int i=end; i>index; i--) {
            nums[i+1] = nums[i];
        }
        nums[index+1] = element;
    }

    public static void main(String[] args) {
        int[] is = new int[]{5,6,7,2};
        insertionSort(is, 0, is.length - 1);
        System.out.println(Arrays.toString(is));
    }

Recursive version:

    public static int[] insertionSort(int[] nums, int begin, int end) {
        if (begin>=end) {
            return nums;
        }

        insertionSort(nums, begin, end-1);
        insert(nums, begin, end-1, nums[end]);

        return nums;
    }

    public static void insert(int[] nums, int begin, int end, int element) {
        int index=end;
        while(index>=begin && nums[index]<element) {
            index--;
        }
        for(int i=end; i>index; i--) {
            nums[i+1] = nums[i];
        }
        nums[index+1] = element;
    }

    public static void main(String[] args) {
        int[] is = new int[]{5,6,7,2};
        System.out.println();
        insertionSort(is, 0, is.length - 1);
        System.out.println(Arrays.toString(is));
    }
user_130141380

The below solution is passing all your test cases. Your insert method should be something like this

public static int[] insertionSort(int[] nums, int begin, int end) {
if (begin >= end) {
    return nums;
}

for (int i = 0; i < end; i++) {
    insert(nums, i, end - 1, nums[end]);
}
return nums;

}

Below is the complete solution for your quick reference.

public class Solution {

public static void main(String[] args) {
    int[] input1 = { 2, 1, 3, -2, 8 };
    int[] result1 = insertionSort(input1, 0, 4);
    printArray(result1);
    int[] input2 = { 2, 6, -4 };
    int[] result2 = insertionSort(input2, 0, 2);
    printArray(result2);
    int[] input3 = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 };
    int[] result3 = insertionSort(input3, 0, 10);
    printArray(result3);
    int[] input4 = { 6, 6, 6, };
    int[] result4 = insertionSort(input4, 0, 2);
    printArray(result4);
    int[] input5 = { 8 };
    int[] result5 = insertionSort(input5, 0, 0);
    printArray(result5);
}

public static void printArray(int[] input) {
    System.out.print("[ ");
    for (int i = 0; i < input.length; i++) {
        System.out.print(input[i] + " ");
    }
    System.out.println("]");
}

public static int[] insertionSort(int[] nums, int begin, int end) {
    if (begin >= end) {
        return nums;
    }

    for (int i = 0; i < end; i++) {
        insert(nums, i, end - 1, nums[end]);
    }
    return nums;
}

static void insert(int[] nums, int begin, int end, int element) {
    int index = end;
    while (index >= begin && nums[index] < element) {
        index--;
    }
    for (int i = end; i > index; i--) {
        nums[i + 1] = nums[i];
    }
    nums[index + 1] = element;
}

}

user_93827950
Related