Answered step by step
Verified Expert Solution
Question
1 Approved Answer
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
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; } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started