Merge Sort and Quick Sort Algorithm analysis

//need help with the second java class files

2 Files:

First java class file includes: //sort.java -merge -mergeSort -partition

-quicksort -isSorted

Second java class file includes: //SortTester.java

1. Method that will use random array of size n for n= 10 100 1000 10000 100000 1000000 20000000 using a random number generator to fill the array with int from 1 to 1000000

2. show run times of both algorithms by timing the above step using the java function System.nanoTime()

//code for merge sort and quick sort algorithms

//need help with the second java class files

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) {

//1. Show mergeSort and QuickSort sort the array { 34, 67, 23, 19, 122, 300, 2, 5, 17, 18, 5, 4 3 19, -40, 23 }

}