MergeSort and Quicksort Java code analysis create a Java class to analyze and co
ID: 3887576 • Letter: M
Question
MergeSort and Quicksort Java code analysis
create a Java class to analyze and compare the mergesort and quicksort algorithms. The sort required is always from smallest value to largest value. Your source code file must be named Sorts.java. Java class methods must match the specifications in the class outline below
1. Create a static Java method, called merge, that merges two sorted lists of integers into a single sorted list
2. Create a static Java method, called mergeSort, that implements a mergesort algorithm that sorts an array of n integers.
3. Create a static partition method that implements the in-place partition algorithm for quicksort
4. Create a static method quickSort that implements the in-place quick sort
5. Create a java method, called isSorted, that tests if an array of integers is sorted in increasing order.
Test your merge, mergeSort, partition, quickSort methods thoroughly to make sure that they are correct; ie they can sort arrays of random values of various lengths. Test your isSorted method too, Make sure to print out the results of the sorts for smaller arrays to visually check that the arrays are sorted.
Experiment #1: Design an experiment to determine which of mergesort or quicksort is the faster sorting algorithm on a on integer arrays of random numbers? Does your answer depend on the size of the array?
Use random arrays of size n, for n = 10, 100, 1000, 10000, 100000, 1000000, 2000000. Use a random number generator to fill your array with integers between 1 and 1000000. For each n, run 20 trials to compare speeds of mergeSort and quickSort. For example, if n = 100, runt mergeSort and quickSort on 20 different arrays of 100 random numbers. For each n, report the number of wins for mergeSort and the number of wins for quickSort. Your program should print out the information to create a table that reports the number of wins for mergeSort and for quicksort as a function of n
Experiment #2 Show that runtimes of mergeSort and quicksort are O(n*log2(n) ) by timing the runs in Experiment #1 by using the java function System.nanoTime().
Computer printout (from Sort.java main program) that shows that quickSort and mergeSort sort the following array.
{ 34, 67, 23, 19, 122, 300, 2, 5, 17, 18, 5, 4319, -40, 23}
public class Sorts
{
//returns true only if a is sorted from smallest to largest values
public static boolean isSorted( int[] a)
/* --------------------MergeSort --------------------*/
//merges sorted slices a[i.. j] and a[j + 1 … k] for 0<= i <=j < k < a.length
public static void merge ( int[] a int i, int j , int k) { }
//sorts a[ i .. k] for 0<=i <= k < a.length
public static void mergeSort(int[] a, int i , int k) { }
//Sorts the array a using mergesort
public static void mergeSort(int[] a ) { }
/* ---------- QuickSort ---------------------------------------------- */
//Implements in-place partition from text. Partitions subarray s[a..b] into s[a..l-1] and s[l+1..b] // so that all elements of s[a..l-1] are less than each element in s[l+1..b]
public static int partition ( int[] s, int a , int b ) { }
//quick sorts subarray a[i..j]
public static void quickSort ( int[] a, int i, int j) { }
//quick sorts array a
public static void quickSort( int[] a) { }
}
Explanation / Answer
Below is your code: -
public class Sorts {
// returns true only if a is sorted from smallest to largest values
public static boolean isSorted(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1])
return false;
}
return true;
}
/* --------------------MergeSort -------------------- */
// merges sorted slices a[i.. j] and a[j + 1 … k] for 0<= i <=j < k <
// a.length
public static void merge(int a[], int l, int m, int r) {
// Find sizes of two subArrays to be merged
int nL = m - l + 1; // for left sub-array
int nR = r - m; // for right sub-array
/*
* create temp Arrays left[] and right[] and copy data from main Array
*/
int left[] = new int[nL];
int right[] = new int[nR];
for (int i = 0; i < nL; ++i)
left[i] = a[l + i];
for (int j = 0; j < nR; ++j)
right[j] = a[m + 1 + j];
/* Merge the temp Arrays back into A[l..r] */
// Initial indexes of first and second sub-Arrays
int i = 0, j = 0;
int k = l; // Initial index of merged sub-array
/*
* Comparing left[] and right[], sub-Array with smaller element get copy
* to main Array A[]
*/
while (i < nL && j < nR) {
if (left[i] <= right[j]) {
a[k] = left[i];
i++;
} else {
a[k] = right[j];
j++;
}
k++;
}
/* Copy remaining elements of left[] if any */
while (i < nL) {
a[k] = left[i];
i++;
k++;
}
/* Copy remaining elements of right[] if any */
while (j < nR) {
a[k] = right[j];
j++;
k++;
}
}
// sorts a[ i .. k] for 0<=i <= k < a.length
public static void mergeSort(int A[], int l, int r) {
if (l < r) {
int mid = (l + r) / 2; // Find the middle index
mergeSort(A, l, mid); // Firstly left half is recursively call
mergeSort(A, mid + 1, r); // Then right half is recursively call
merge(A, l, mid, r); // Merge the sorted halves
}
}
// Sorts the array a using mergesort
public static void mergeSort(int[] a) {
mergeSort(a, 0, a.length - 1);
}
/* ---------- QuickSort ---------------------------------------------- */
// Implements in-place partition from text. Partitions subarray s[a..b] into
// s[a..l-1] and s[l+1..b] // so that all elements of s[a..l-1] are less
// than each element in s[l+1..b]
public static int partition(int[] a, int first, int last) {
int n = (int) (Math.random() * (last - first + 1)) + first;
swap(a, first, n);
int i = first + 1;
int j = last;
// {I: a[first+1,i) <= a[first], a(j..last] > a[first]}
while (i <= j) {
if (a[i] <= a[first])
++i;
else {
swap(a, i, j);
--j;
}
}
swap(a, first, j);
return j;
}
public static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
// quick sorts subarray a[i..j]
public static void quickSort(int[] a, int first, int last) {
if (first >= last)
return;
int k = partition(a, first, last);
quickSort(a, first, k - 1);
quickSort(a, k + 1, last);
}
// quick sorts array a
public static void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}
public static void main(String[] args) {
int arr[] = { 34, 67, 23, 19, 122, 300, 2, 5, 17, 18, 5, 4319, -40, 23};
quickSort(arr);
System.out.println("Is array sorted : "+isSorted(arr));
int arr2[] = { 34, 67, 23, 19, 122, 300, 2, 5, 17, 18, 5, 4319, -40, 23};
mergeSort(arr2);
System.out.println("Is array sorted : "+isSorted(arr2));
}
}