Expand SortingAll.java to have methods of all sorting algorithms for String objects. Given an array of single character strings, print the quicksort result after each partition call.

import java.util.*; //Implement //selection sort, insertion sort, (easy, n^2) //merge sort (harder, n log n) //quick sort (easy, average is n log n, widely used) //priority queues (harder, n logn) public class SortingAll { public static void main(String[] args) { //Given an array //int[] a = {4, 6, 7, 0, 3, 9, 3, 6}; int SIZE = 100000; int [] a = new int[SIZE]; for (int i = 0; i < a.length; i++) a[i] = (int) (Math.random() * 134); long startTime = System.currentTimeMillis(); //System.out.println("before selection sort: " + Arrays.toString(a)); selection(a); //System.out.println("after selection sort:" + Arrays.toString(a)); long endTime = System.currentTimeMillis(); System.out.println("selection sort time: " + (endTime-startTime)); //shuffle, sort again shuffle(a); startTime = System.currentTimeMillis(); //System.out.println("before insertion sort: " + Arrays.toString(a)); insertion(a); //System.out.println("after insertion sort:" + Arrays.toString(a)); endTime = System.currentTimeMillis(); System.out.println("insertion sort time: " + (endTime-startTime)); //shuffle, sort again shuffle(a); startTime = System.currentTimeMillis(); //System.out.println("before merge top down sort: " + Arrays.toString(a)); mergeTD(a); //System.out.println("after merge top down sort:" + Arrays.toString(a)); endTime = System.currentTimeMillis(); System.out.println("merge sort time: " + (endTime-startTime)); //shuffle, sort again shuffle(a); startTime = System.currentTimeMillis(); //System.out.println("before merge buttom up sort: " + Arrays.toString(a)); mergeBU(a); //System.out.println("after merge buttom up sort:" + Arrays.toString(a)); endTime = System.currentTimeMillis(); System.out.println("merge sort BU time: " + (endTime-startTime)); //shuffle, sort again shuffle(a); startTime = System.currentTimeMillis(); //System.out.println("before quick sort: " + Arrays.toString(a)); quickSort(a, 0, a.length-1); //System.out.println("after quick sort:" + Arrays.toString(a)); endTime = System.currentTimeMillis(); System.out.println("quick sort time: " + (endTime-startTime)); } public static void shuffle(int[] a) { //shuffle an array for the next sort for (int i = 0; i < a.length; i++) { int k = (int) (Math.random() * a.length); int tmp = a[i]; a[i] = a[k]; a[k] = tmp; } } public static void selection(int[] a) { //start from the beginning as unsorted sub array for (int i = 0; i < a.length; i++) { int k = i; //find the smallest in the unsorted for (int j = i+1; j < a.length; j++) { if (a[j] < a[k]) { k = j; } } //swap to place the min at the beginning int tmp = a[i]; a[i] = a[k]; a[k] = tmp; } } public static void insertion(int[] a) { //pick the beginning one of the unsorted sub array for (int i = 0; i < a.length; i++) { //insert into the proper position of the sorted // sub array int j, tmp = a[i]; for (j = i-1; j >= 0; j--) { if (a[j] <= tmp) { break; } //shift larger one to the right a[j+1] = a[j]; } //insert i into the position a[j+1] = tmp; } } public static void merge(int[] a, int start, int mid, int end) { //need another array to hold the original value int[] b = new int[a.length]; //merge a[start,...,mid] and a[mid+1,..., end] int i = start, j = mid+1; int k; for (k = start; k <= end; k++) { b[k] = a[k]; } for (k = start; k <= end; k++) { if (i > mid) a[k] = b[j++]; else if (j > end) a[k] = b[i++]; else if (b[j] < b[i]) a[k] = b[j++]; else a[k] = b[i++]; } } public static void mergeTD(int[] a) { //top down mergeSort(a, 0, a.length-1); } private static void mergeSort(int[] a, int start, int end) { if (start >= end) return; int mid = start + (end - start) / 2; mergeSort(a, start, mid); mergeSort(a, mid+1, end); merge(a, start, mid, end); } public static void mergeBU(int[] a) { //each element is sorted at the beginning //keep merge sub sorted array int n = a.length; int len, start; for (len = 1; len < n; len *= 2) { for (start = 0; start < n - len; start += 2*len) { merge(a, start, start+len-1, Math.min(start+2*len-1, n-1)); } } } public static void quickSort(int[] a, int start, int end) { if (start >= end) return; int j = partition(a, start, end); quickSort(a, start, j-1); quickSort(a, j+1, end); } private static int partition(int[] a, int start, int end) { int i = start, j = end+1; int key = a[start]; while (true) { //scan right to find smaller one while (a[++i] < key) { if (i == end) break; //reach the end } while (a[--j] > key) { if (j == start) break; } if (i >= j) break; //swap i and j int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } //swap start and j int tmp = a[j]; a[j] = a[start]; a[start] = tmp; //System.out.println(j + Arrays.toString(a)); return j; } }