Show fully functional Java code and screenshots of outputs. Please properly label each question, package and file. This is an all inclusive question.

Close Lab 2: Sorting In this lab, we will work on variations of the sorting algorithms that we learned in class. 1. In the selection sort that we discussed in class is to locate the smallest element in a list ai, a2, . .., an and move it to the beginning of the list during each round. A variation of the algorithm is to locate both the smallest and the largest elements and move them to the beginning and the end of the list during each round. For example, at the second round, the process is repeated for the sublist of a2, ..., 09-1, and so on. We can call this selection sort as double-ended selection sort. Add a new method in unit 2 example MyArray.java, which will conduct the above defined double-ended selection sort. Then in the class example JavaSortingEx.java, add your codes to test it. 2. The quicksort algorithm discussed in class example MyArray.java selects the first element in the list as the pivot. Revise the method by selecting the median among the first, middle, and the last element in the list(the median-of-three rule). Please test your revised method. 3. The quicksort algorithm discussed in class example MyArray.java is implemented as a recursive method. Rewrite the method as a non-recursive method using stack. Please test your revised method. 4. The mergesort algorithm discussed in class example MyArray.java is implemented in 2-way merge. Rewrite the method in a 3-way merge. In 3-way merge, instead of splitting the list into two halves, it is split into three thirds. Then we recursively sort each third and merge them. Rewrite the method implemented in 3-way merge and test it. package javasortingex; /** * @author ziping */ public class JavaSortingEx { /** @param args the command line arguments public static void main(String[] args) { MyArray A = new MyArray(Integer.class); for(int i = 0; i B = new MyArray(Integer.class); for(int i = 0; i C = new MyArray(Integer.class); for(int i = 0; i D = new MyArray(Integer.class); for(int i = 0; i D = new MyArray(Integer.class); D.Insert(69, 0); D. Insert(35, 1); D. Insert (18, 2); D.Insert(87, 3); D.Insert(50, 4); D. Insert(58, 5); D. Insert(79, 6); System.out.println(" ShellSort"); for(int i = 0; i E = new MyArray(Integer.class); for(int i = 0; i F = new MyArray(Integer.class); for(int i = 0; i > { private T[] arr; private int size; public static final int CAPACITY = 15; public MyArray(Class type) { // needs to use reflect. Array.newInstance() to initiate // an array of bounded type arr = (T[]) java.lang.reflect. Array.newInstance(type, CAPACITY); } public I get(int index) { return arr[index]; } public int size(){ return size; } public void Insert(I item, int index) { if (size + 1 > CAPACITY) throw new ArrayIndexOutOfBoundsException(); else if (index > size) throw new ArrayIndexOutOfBoundsException(); else{ for (int i = size; i > index + 1; i--) arr[i] = arr[i-1]; arr[index] = item; size++; } } public void Delete(int index) { if (index > size - 1) throw new ArrayIndexOutOfBoundsException(); else{ for (int i = index; i 0){ I temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; Sorted = false; } } } public void SelectionSort({ int best; for (int i = 0; i 0) best = j; if (i != best){//swap the two items I temp = arr[i]; arr[i] = arr[best]; arr[best] = temp; } } } public void InsertionSort(){ int key, location; I temp; for (key = 1; key && arr[location - 1].compareTo(temp) > 0); arr[location] = temp; } } } public void Quicksort(int first, int last) { if (first 0) right--; while (left 0; gap 1= 2 ) for( int i = gap; i gap && tmp.compareTo(arr[ j - gap ]) type, int low, int high) { if (low type, int low, int middle, int high) private //merge with low and high T[] tem = (T[]) java.lang.reflect. Array.newInstance(type, high-low+1); int lowin = low, highin = middle + 1, temin = 0; while (lowin A = new MyArray(Integer.class); for(int i = 0; i B = new MyArray(Integer.class); for(int i = 0; i C = new MyArray(Integer.class); for(int i = 0; i D = new MyArray(Integer.class); for(int i = 0; i D = new MyArray(Integer.class); D.Insert(69, 0); D. Insert(35, 1); D. Insert (18, 2); D.Insert(87, 3); D.Insert(50, 4); D. Insert(58, 5); D. Insert(79, 6); System.out.println(" ShellSort"); for(int i = 0; i E = new MyArray(Integer.class); for(int i = 0; i F = new MyArray(Integer.class); for(int i = 0; i > { private T[] arr; private int size; public static final int CAPACITY = 15; public MyArray(Class type) { // needs to use reflect. Array.newInstance() to initiate // an array of bounded type arr = (T[]) java.lang.reflect. Array.newInstance(type, CAPACITY); } public I get(int index) { return arr[index]; } public int size(){ return size; } public void Insert(I item, int index) { if (size + 1 > CAPACITY) throw new ArrayIndexOutOfBoundsException(); else if (index > size) throw new ArrayIndexOutOfBoundsException(); else{ for (int i = size; i > index + 1; i--) arr[i] = arr[i-1]; arr[index] = item; size++; } } public void Delete(int index) { if (index > size - 1) throw new ArrayIndexOutOfBoundsException(); else{ for (int i = index; i 0){ I temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; Sorted = false; } } } public void SelectionSort({ int best; for (int i = 0; i 0) best = j; if (i != best){//swap the two items I temp = arr[i]; arr[i] = arr[best]; arr[best] = temp; } } } public void InsertionSort(){ int key, location; I temp; for (key = 1; key && arr[location - 1].compareTo(temp) > 0); arr[location] = temp; } } } public void Quicksort(int first, int last) { if (first 0) right--; while (left 0; gap 1= 2 ) for( int i = gap; i gap && tmp.compareTo(arr[ j - gap ]) type, int low, int high) { if (low type, int low, int middle, int high) private //merge with low and high T[] tem = (T[]) java.lang.reflect. Array.newInstance(type, high-low+1); int lowin = low, highin = middle + 1, temin = 0; while (lowin