Compare five sorting algorithms: Insertion Sort, Selection Sort, Bubble Sort, Merge Sort, and QuickSort. Pseudo code for the sorting algorithms are given below

Algorithm 1 InsertionSort(A) for i = 1, , n do val = A[i] position = i while position > 1 and A[position 1] > val do A[position] = A[position 1] position = position 1 end while A[position] = val end for

Algorithm 2 SelectionSort(A) for i = 1, , n 1 do imin = i for j = i + 1, , n do if A[j] < A[imin] then imin = j end if end for if imin i then swap A[i] with A[imin] end if end for

Algorithm 3 BubbleSort(A) swapped = true while swapped do swapped = false for i = 2, , n do if A[i 1] > A[i] then swap A[i 1] with A[i] swapped = true end if end for n = n 1 end while

Algorithm 4 MergeSort(A) if n = 1 then return A end if mid = [n/2] L = MergeSort(A[1, , mid]) R = MergeSort(A[mid + 1, , n]) return Merge(L, R) Merge(L, R) l = length(L) r = length(R) i,j,k = 1 while i l and j r do if L[i] > R[j] then C[k] = R[j] j = j + 1 else C[k] = L[i] i = i + 1 end if k = k + 1 end while if i l then copy L[i, , l] to the end of C end if if j r then copy R[j, , r] to the end of C end ifreturn C

Algorithm 5 QuickSort(A,low,high) if low < high then p = Partition(A,low,high) QuickSort(A,low, p 1) QuickSort(A, p + 1, high) end if Partition(A,low,high) pivot = A[high] i = low for j = low, , high 1 do if A[j] < pivot then swap A[i] with A[j] i = i + 1 end if end for swap A[i] with A[h] return i

Write a program to estimate the running time of ve sorting algorithms. Your program (test) should run in command line. It takes three arguments: name of the sorting method (chosen from selection, insertion, bubble, merge, and quick), number of arrays to be sorted, and the size of each array. Your program will generate the given number of random double array of the given size, sort the array using the specied method, and output the average running time in milliseconds (1ms = 103 second). You may use System.nanoTime() to measure the running time of a sorting method (do not measure the time to generate all random arrays). The run time is measured approximately. If you sort a single small array, the run time is likely to be reported as a very small number, even zero. To get a more accurate run time, you can sort more arrays. For example, you can set the number of arrays to 1000 and then divide the reported run time by 1000 to get the average time it took to sort each of the arrays. For instance, the following command, java test merge 1000 2000 outputs the average running time of sorting an array of size 2000 using 1000 random arrays