Merge Arrays and Merge Sort ----------------------------------------------------
ID: 3840317 • Letter: M
Question
Merge Arrays and Merge Sort
----------------------------------------------------
Fill in the TODO area and documentation area. The source codes are down below:
------------------------------------------------------------------
public class LAB1 {
// TODO: document this method
public static int[] insertionSort(int[] a) {
//TODO: implement this method
for (int i = 1; i < a.length; i++) {
int element = a[i];
int j = i;
while (j > 0 && a[j -1] > element){
a[j] = a[j -1];
j--;
}
a[j] = element;
}
return a;
}
// TODO: document this method
public static int[] mergeSort(int[] a) {
//TODO: implement this method
return null;
}
//Subroutine to merge two subarrays
public static int[] merge(int[] a1, int[] a2) {
//TODO: implement this method
return null;
}
/********************************************
*
* Do NOT modify anything below
*
********************************************/
public final static int MAX_INPUT = 524287;
public final static int MIN_INPUT = 0;
/* Implementation note: The "system" sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch.
* This algorithm offers O(n log(n)) performance on many data
* sets that cause other quicksorts to degrade to quadratic performance,
* and is typically faster than traditional (one-pivot) Quicksort implementations.
*/
public static int[] systemSort(int[] a) {
Arrays.sort(a);
return a;
}
// read ints from a Scanner
// returns an array of the ints read
private static int[] getInts(Scanner s) {
ArrayList a = new ArrayList();
while (s.hasNextInt()) {
int i = s.nextInt();
if ((i <= MAX_INPUT) && (i >= MIN_INPUT))
a.add(i);
}
return toIntArray(a);
}
// copies an ArrayList of Integer to an array of int
private static int[] toIntArray(ArrayList a) {
int[] ret = new int[a.size()];
for(int i = 0; i < ret.length; i++)
ret[i] = a.get(i);
return ret;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.printf("Enter the sorting algorithm to use ([i]nsertion, [m]erge, or [s]ystem): ");
char algo = s.next().charAt(0);
System.out.printf("Enter the integers that you would like sorted, followed by a non-integer character: ");
int[] unsorted_values = getInts(s);
int[] sorted_values = {};
s.close();
switch (algo) {
case 'm':
sorted_values = mergeSort(unsorted_values);
break;
case 'i':
sorted_values = insertionSort(unsorted_values);
break;
case 's':
sorted_values = systemSort(unsorted_values);
break;
default:
System.out.println("Invalid sorting algorithm");
System.exit(0);
break;
}
System.out.println(Arrays.toString(sorted_values));
}
}
Explanation / Answer
int []mergeSort(unsorted_values) {
int[] tmp = Arrays.copyOf(unsorted_values, unsorted_values.length);
mergeSort(tmp,0,tmp.length - 1);
}
void mergeSort(int arr[], int l, int r) { //to sort arrray from index l(eft) to r(ight)
if (l < r) {
int m = (l+r)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
//once sorted merge them
merge(arr, l, m, r);
}
}
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1; //size of independent array
int n2 = r - m;
/* tmp arrays */
int L[n1], R[n2];
// Copy data to tmp arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
// Merge the temp arrays back into arr[l..r]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* cpy left over elements of L[], if there
are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
This three methods will handle merge sort for you.