java programming. 1. In the selection sort that we discussed in class is to locate the smallest element in a list a1, a2, . . ., anand move it to the beginning of the list during each round. A variation ofthe 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, . . ., an-1, andso on. We can call this selection sort as double-ended selection sort. Add a new method in unit 2example MyArray.java, which will conduct the above defined double-ended selection sort. Then in the class exampleJavaSortingEx.java, add your codes to test it. MyArray.java public class MyArray> { 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 T get(int index){ return arr[index]; } public int size(){ return size; } public void Insert(T 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 < size - 1; i++) arr[i] = arr[i+1]; size--; } } public void BubbleSort(){ boolean Sorted = false; while (!Sorted){ Sorted = true; for (int i = 0; i < size - 1; i++) if (arr[i].compareTo(arr[i+1]) > 0){ T temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; Sorted = false; } } } public void SelectionSort(){ int best; for (int i = 0; i < size-1; i++){ best = i; for (int j = i+1; j < size; j++) if (arr[best].compareTo(arr[j]) > 0) best = j; if (i != best){//swap the two items T temp = arr[i]; arr[i] = arr[best]; arr[best] = temp; } } } public void InsertionSort(){ int key, location; T temp; for(key = 1; key < size; key++){ if(arr[key].compareTo(arr[key - 1]) < 0){ temp = arr[key]; location = key; do //right shift all elements that are greater than key element one slot { arr[location] = arr[location - 1]; location--; }while(location > 0 && arr[location - 1].compareTo(temp) > 0); arr[location] = temp; } } } public void Quicksort(int first, int last){ if (first < last){ int pivotIndex = Split(first, last); Quicksort(first, pivotIndex - 1); Quicksort(pivotIndex + 1, last); } } private int Split(int first, int last){ int pivotIndex; T pivot = arr[first]; int left = first, right = last; while (left < right){ while (arr[right].compareTo(pivot) > 0) right--; while (left < right && arr[left].compareTo(pivot) <= 0) left++; if (left < right){//swap the two items T temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } } T temp = arr[first]; arr[first] = arr[right]; arr[right] = temp; pivotIndex = right; return pivotIndex; } public void ShellSort(){ int j; for( int gap = size / 2; gap > 0; gap /= 2 ) for( int i = gap; i < size; i++ ){ T tmp = arr[ i ]; for( j = i; j >= gap && tmp.compareTo(arr[ j - gap ]) < 0; j -= gap ){ arr[ j ] = arr[ j - gap ]; } arr[ j ] = tmp; for(T var: arr) if(var != null) System.out.print(var + ", "); System.out.println(); } } public void MergeSort(Class type, int low, int high){ if (low < high){ int middle = (low + high) / 2; MergeSort(type, low, middle); MergeSort(type, middle+1, high); Merge(type, low, middle, high); } } private void Merge(Class type, int low, int middle, int high) { //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 <= middle && highin <= high){ if (arr[lowin].compareTo(arr[highin]) < 0) tem[temin++] = arr[lowin++]; else tem[temin++] = arr[highin++]; } while (lowin <= middle){ tem[temin++] = arr[lowin++]; } while ( highin <= high){ tem[temin++] = arr[highin++]; } for (int i=0; i < high-low+1; i++) arr[low+i] = tem[i]; } } 

JavaSortingEx.java,

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 < MyArray.CAPACITY; i++) A.Insert((int)(Math.random() * (999 - 0)), i); System.out.println("BubbleSort"); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(A.get(i) + ", "); System.out.println(); A.BubbleSort(); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(A.get(i) + ", "); System.out.println(); MyArray B = new MyArray(Integer.class); for(int i = 0; i < MyArray.CAPACITY; i++) B.Insert((int)(Math.random() * (999 - 0)), i); System.out.println(" InsertionSort"); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(B.get(i) + ", "); System.out.println(); B.InsertionSort(); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(B.get(i) + ", "); System.out.println(); MyArray C = new MyArray(Integer.class); for(int i = 0; i < MyArray.CAPACITY; i++) C.Insert((int)(Math.random() * (999 - 0)), i); System.out.println(" SelectionSort"); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(C.get(i) + ", "); System.out.println(); C.SelectionSort(); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(C.get(i) + ", "); System.out.println(); /* MyArray D = new MyArray(Integer.class); for(int i = 0; i < MyArray.CAPACITY; i++) D.Insert((int)(Math.random() * (999 - 0)), i); System.out.println(" ShellSort"); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(D.get(i) + ", "); System.out.println(); D.ShellSort(); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(D.get(i) + ", "); System.out.println(); */ MyArray 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 < D.size(); i++) System.out.print(D.get(i) + ", "); System.out.println(); D.ShellSort(); for(int i = 0; i < D.size(); i++) System.out.print(D.get(i) + ", "); System.out.println(); MyArray E = new MyArray(Integer.class); for(int i = 0; i < MyArray.CAPACITY; i++) E.Insert((int)(Math.random() * (999 - 0)), i); System.out.println(" QuickSort"); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(E.get(i) + ", "); System.out.println(); E.Quicksort(0, E.size() - 1); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(E.get(i) + ", "); System.out.println(); MyArray F = new MyArray(Integer.class); for(int i = 0; i < MyArray.CAPACITY; i++) F.Insert((int)(Math.random() * (999 - 0)), i); System.out.println(" MergeSort"); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(F.get(i) + ", "); System.out.println(); F.MergeSort(Integer.class, 0, F.size() - 1); for(int i = 0; i < MyArray.CAPACITY; i++) System.out.print(F.get(i) + ", "); System.out.println(); } }