Java Algorithm: Merge() and MergeSort() ----------------------------------- NOTE
ID: 3840733 • Letter: J
Question
Java Algorithm: Merge() and MergeSort()
-----------------------------------
NOTE: ONLY fill in the TODO part, then provide explanation. Do NOT change codes outside of the Merge() and MergeSort() method.
The following source code:
------------------------------------
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<Integer> a = new ArrayList<Integer>();
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<Integer> 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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class LAB1 {
// TODO: document this method
// function to sort the element using insertion sort
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
// function to sort the element using merge sort
public static int[] mergeSort(int[] a) {
//TODO: implement this method
int a1[] = new int[a.length / 2];
int a2[]= new int[a.length - a1.length];
System.out.println(a1.length+" "+a2.length);
int j=0;
for(int i=0;i<a1.length;i++){
a1[i] = a[j];
j++;
}
for(int i=0;i<a2.length;i++){
a2[i] = a[j];
j++;
}
Arrays.sort(a1);
Arrays.sort(a2);
int array[] = merge(a1,a2);
return array;
}
//Subroutine to merge two subarrays
public static int[] merge(int[] a1, int[] a2) {
//TODO: implement this method
int k = 0;
int l = 0;
int j = 0;
int array[] = new int[a1.length+a2.length];
while (k < a1.length && l < a2.length) {
if (a1[k] < a2[l]) {
array[j] = a2[k];
k++;
}
else {
array[j] = a2[l];
l++;
}
j++;
}
System.arraycopy(a1, k, array, j, a1.length-k);
System.arraycopy(a2, l, array, j, a2.length-l);
return array;
}
/********************************************
*
* 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<Integer> a = new ArrayList<Integer>();
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<Integer> 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));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.