I need help with the following Java code Note that all methods must use recursio
ID: 3906510 • Letter: I
Question
I need help with the following Java code
Note that all methods must use recursion. Feel free to add any helper methods you deem necessary.
Thanks for all the help : D
/**
* Simple sorting algorithms' implementations. Note that it is
* fine to create private helper methods inside this class.
* However, you are not allowed to have an instance or class
* variables.
*/
public class SimpleSorts
{
/**
Sorts an array using the insertion sort method */
public static void insertionSortRec(int arr[]) {
int len = arr.length;
for (int l = 1; l < len; l++) {
int key = arr[l];
int k = l-1;
//inserts larger element at the correct index
while ( (k > -1) && ( arr [k] > key ) ) {
arr [k+1] = arr [k];
k--;
}
arr[k+1] = key;
}
}
/**
* Sorts entries of array "arr" using recursive insertion
* sort algorithm in nondecreasing order. You can assume
* that array won't be null and will have at least 2 elements.
*/
public static void insertionSortRec(int[] arr) //the first method gives an example of the non recurisve form of this method
{
insertionHelper(arr,1); //TODO should it be 1 or 0 here
}
/**
* Helper method for the insertionSortRec that sorts
* a list of values by repeatedly inserting a new
* element into a sorted sub list until the whole list is
* sorted.
*/
public static int[] insertionHelper(int[] arr, int index)
{
//TODO
}
/**
* A bubble sort can sort an array of n entries into nondecreasing order
* by making n-1 passes through the array. On each pass, it compares adjacent
* entries and swaps them if they are out of order. For example, on the first
* pass, it compares the first and second entries, then the second and third
* entries, and so on. At the end of the first pass, the largest entry is in
* its proper position at the end of the array. We say that it has bubbled to
* its correct spot. Each subsequent pass ignores the entries at the end of the
* array, since they are sorted and are larger than any of the remaining entries.
* Thus, each pass makes one fewer comparison than the previous pass.
*
* Here is an example of a bubble sort.
* (Numbers in parentheses represent sorted subarray.)
* Original array: 8 2 6 4 9 7 1
* After pass 1 : 2 6 4 8 7 1 (9)
* After pass 2 : 2 4 6 7 1 (8 9)
* After pass 3 : 2 4 6 1 (7 8 9)
* After pass 4 : 2 4 1 (6 7 8 9)
* After pass 5 : 2 1 (4 6 7 8 9)
* After pass 6 : 1 (2 4 6 7 8 9)
*
* Here is the detail of pass 1.
* (Square brackets indicate currently compared entries of array.)
*
* Original array: 8 2 6 4 9 7 1
* Step 1 : [8 2] 6 4 9 7 1 compare 1st and 2nd; swap
* Step 2 : 2 [8 6] 4 9 7 1 compare 2nd and 3rd; swap
* Step 3 : 2 6 [8 4] 9 7 1 compare 3rd and 4th; swap
* Step 4 : 2 6 4 [8 9] 7 1 compare 4th and 5th; no swap
* Step 5 : 2 6 4 8 [9 7] 1 compare 5th and 6th; swap
* Step 6 : 2 6 4 8 7 [9 1] compare 6th and 7th; swap
* Step 7 : 2 6 4 8 7 1 9 steps repeated at next pass.
*
* For more info check: https://en.wikipedia.org/wiki/Bubble_sort
* Note: It is OK to reuse their pseudocode ideas.
*/
/**
* Sorts entries of array "arr" using recursive bubble
* sort algorithm in nondecreasing order. You can assume
* that array won't be null and will have at least 2 elements.
*/
public static void bubbleSortRec(int[] arr)
{
}
}
* Lec xy D Po x . * Exe × . el N: × , el N. × e Che x e Giv x , el N' × @ Ge. × a Am × 121 × C D file://c:/users/DARNESHA.9620RANDLE/Downloads/sorting-part1.pdf PowerPoint Presentation 2033 Insertion Sort int [ ] myList {2, 9, 5, 4, 8, 1. 6); // Unsorted Step 1: Initially, the sorted sublist contains the first element in the list. Insert 9 into the sublist The insertion sort algorithm sorts a list of values by repeatedly inserting a new element into a sorted sublist until the whole list is sorted Step2: The sorted sublist is (2,9. Insert 5 into the sublist. ?5 4 Step 3: The sorted sublist is (2, 5,9. Insert 4 into the sublist. 2 59-4 81 6 Step 4: The sorted sublist is {2,4,5,9}·Insert 8 into the sublist. 24 5 '?8 1 6 Step 5: The sorted sublist is (2,4, 5,8,9.Insert 2586 1 into the sublist. Step 6: The sorted sublist is {1, 2, 4, 5, 8, 9] Insert 6 into the sublist. Step 7: The entire list is now sorted. 1 2456 8 9 8:29 PM 6/19/2018 Type here to search ^Explanation / Answer
public static int[] insertionHelper(int[] arr, int index)
{
if (n <= 1)
return;
insertionHelper( arr, n-1 );
int last = arr[n-1];
int j = n-2;
while (j >= 0 && arr[j] > last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
public static void insertionSortRec(int[] arr)
{
insertionHelper(arr,arr.length);
}
static void bubbleSortHelper(int arr[], int n)
{
if (n == 1)
return;
for (int i=0; i<n-1; i++)
if (arr[i] > arr[i+1])
{
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
bubbleSortHelper(arr, n-1);
}
public static void bubbleSortRec(int[] arr)
{
bubbleSortHelper(arr, arr.length);
}