Implement the mergesort algorithm using Java generics. Description First, downlo
ID: 3759762 • Letter: I
Question
Implement the mergesort algorithm using Java generics.
Description
First, download the driver and dictionary files, and place them in your project directory
Create a class MergeSorter.java that implements the mergesort algorithm in a generic way (i.e. over items that extend the Java Comparable interface). You may use this file as a template. Your goal is twofold:
• Genericize the mergesorter class using ArrayLists rather than arrays.
• Fill in the recursive portion of the mergesort algorithm within the `mergesort' method (annotated for you)
In addition, the driver times the speed of your mergesort algorithm. After you have completed the above, you should try using LinkedLists rather than ArrayLists, and see how the time changes.
NOTE: Be careful with your parameters to ensure they will only take types of List, and not ArrayList
Example Dialog
Checking merge algorithm:
Success!
Initial (int) array of size 76066 is sorted: false
Mergesort: 214.883256 ms
Integer array sort successful.
Simple string sort:
the quick brown fox jumps over the lazy dog
brown dog fox jumps lazy over quick the the
Initial (String) array of size 57578 is sorted: false
Mergesort: 192.520276 ms
String array sort successful.
Note
The driver is randomized, so your output will be different
THIS IS THE “TEMPLATE” THAT IS GIVEN TO USE TO GO BY:
public class MergeSorter {
/**
* Sort an array using the `mergesort' algorithm.
* @param array The array to sort.
* @return The sorted array
*/
public Integer[] sort(Integer[] array) {
return mergesort(array);
}
/**
* Mergesort recursive algorithm
* @param array The array to sort.
* @return The sorted array
*/
private Integer[] mergesort(Integer[] array) {
/* Part II: For you to complete */
}
/**
* Merge the two arrays.
* @param left The left array to merge
* @param right The right array to merge
* @return The merged array
*/
public Integer[] merge(Integer[] left, Integer[] right) {
int leftI = 0;
int rightI = 0;
int newI = 0;
Integer[] newArr = new Integer[left.length + right.length];
while (leftI < left.length && rightI < right.length) {
if (left[leftI] < right[rightI]) {
newArr[newI] = left[leftI];
leftI++;
} else {
newArr[newI] = right[rightI];
rightI++;
}
newI++;
}
// Either the left or the right may still have elements
for (int i = leftI; i < left.length; i++) { // left
newArr[newI] = left[i];
newI++;
}
for (int i = rightI; i < right.length; i++) { // right
newArr[newI] = right[i];
newI++;
}
return newArr;
}
/**
* Prints the elements of the array, delimited by spaces.
*/
public void printCollection(Integer[] items) {
for (int i = 0; i < items.length; i++) {
System.out.print(items[i] + " ");
}
System.out.println();
}
}
THIS IS THE “DRIVER” FILE THAT SHOULD BE IN DIRECTORY:
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
public class SortTester<E extends Comparable<E>> {
public static final String DICTIONARY_FILE = "dictionary.txt";
public static final int MIN_ARRAY_SIZE = 50000;
public static final int MAX_ARRAY_SIZE = 100000;
public static final int MAX_ELEMENT_SIZE = 1000;
public static final int SORTED_STEP_SIZE = 10;
/**
* Entry point.
*/
public static void main(String[] args) {
System.out.println("Checking merge algorithm:");
MergeSorter<Integer> sorter = new MergeSorter<Integer>();
if (!checkMerge()) {
System.out.println("Failure.");
} else {
System.out.println("Success!");
}
System.out.println();
if (sortIntegers()) {
System.out.println("Integer array sort successful.");
} else {
System.out.println("Integer array sort unsuccessful.");
}
System.out.println();
System.out.println("Simple string sort:");
List<String> starray = new ArrayList<String>();
starray.add("the");
starray.add("quick");
starray.add("brown");
starray.add("fox");
starray.add("jumps");
starray.add("over");
starray.add("the");
starray.add("lazy");
starray.add("dog");
MergeSorter<String> stringsorter = new MergeSorter<String>();
stringsorter.printCollection(starray);
starray = stringsorter.sort(starray);
stringsorter.printCollection(starray);
System.out.println();
if (sortStrings()) {
System.out.println("String array sort successful.");
} else {
System.out.println("String array sort unsuccessful.");
}
}
/**
* Test against a randomly generated array of integers.
*/
private static boolean sortIntegers() {
Random rand = new Random();
int arraySize = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
List<Integer> array = new ArrayList<Integer>();
for (int i = 0; i < arraySize; i++) {
array.add(rand.nextInt(MAX_ELEMENT_SIZE));
}
SortTester<Integer> intTester = new SortTester<Integer>();
System.out.println("Initial (int) array of size " + array.size()
+ " is sorted: " + intTester.checkSorted(array));
long startTime;
long endTime;
MergeSorter<Integer> intsorter = new MergeSorter<Integer>();
startTime = System.nanoTime();
array = intsorter.sort(array);
endTime = System.nanoTime();
long mergeSortTime = endTime - startTime;
double millis = mergeSortTime / 1000000.;
System.out.println("Mergesort: " + millis + " ms");
if (millis > 500) {
System.out.println("Sort too slow, you sure it's mergesort?");
return false;
}
return intTester.checkSorted(array);
}
private static ArrayList<String> readDictionary() {
Scanner fileScan = null;
try {
fileScan = new Scanner(new File(DICTIONARY_FILE));
} catch (FileNotFoundException e) {
System.out.println("Can't find dictionary file.");
System.out.println("Modify the variable 'DICTIONARY_FILE' in SortTester.java");
System.out.println("to point to the correct file (dictionary.txt)");
System.exit(1);
}
ArrayList<String> dictionary = new ArrayList<String>(130000);
while (fileScan.hasNext()) {
dictionary.add(fileScan.next());
}
return dictionary;
}
private static boolean sortStrings() {
ArrayList<String> dictionary = readDictionary();
Random rand = new Random();
int arraySize = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
List<String> array = new ArrayList<String>();
for (int i = 0; i < arraySize; i++) {
array.add(dictionary.get(rand.nextInt(dictionary.size())));
}
SortTester<String> stringTester = new SortTester<String>();
System.out.println("Initial (String) array of size " + array.size()
+ " is sorted: " + stringTester.checkSorted(array));
long startTime;
long endTime;
MergeSorter<String> stringsorter = new MergeSorter<String>();
startTime = System.nanoTime();
array = stringsorter.sort(array);
endTime = System.nanoTime();
long mergeSortTime = endTime - startTime;
double millis = mergeSortTime / 1000000.;
System.out.println("Mergesort: " + millis + " ms");
if (millis > 500) {
System.out.println("Sort too slow, you sure it's mergesort?");
return false;
}
return stringTester.checkSorted(array);
}
/**
* Checks if an ArrayList is sorted in ascending order.
* @param array The array to verify.
* @return True if the array is sorted, false otherwise
*/
public boolean checkSorted(List<E> array) {
for (int i = 1; i < array.size(); i ++) {
if (array.get(i).compareTo(array.get(i - 1)) < 0) {
return false;
}
}
return true;
}
public static boolean checkMerge() {
// Generate two arbitrary arrays
Random rand = new Random();
int arr1Size = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
int arr2Size = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
ArrayList<Integer> arr1 = generateSortedArray(arr1Size);
ArrayList<Integer> arr2 = generateSortedArray(arr1Size);
MergeSorter<Integer> intMerger = new MergeSorter<Integer>();
ArrayList<Integer> merged = intMerger.merge(arr1, arr2);
SortTester<Integer> intTester = new SortTester<Integer>();
return intTester.checkSorted(merged);
}
public static ArrayList<Integer> generateSortedArray(int size) {
ArrayList<Integer> arr = new ArrayList<Integer>();
Random rand = new Random();
Integer prevElement = 0;
for (int i = 0; i < size; i++) {
Integer newElement = prevElement + rand.nextInt(SORTED_STEP_SIZE);
arr.add(newElement);
prevElement = newElement;
}
return arr;
}
}
THE DICTIONARY FILE THAT SHOULD BE IN DIRECTORY:
This file is basically all the letters at the top left and right of an actual dictionary
And it is super long so I didn’t include it here. ( Comment if you need the dictionary driver and I will add it.)
Explanation / Answer
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
public class SortTester<E extends Comparable<E>> {
public static final String DICTIONARY_FILE = "dictionary.txt";
public static final int MIN_ARRAY_SIZE = 50000;
public static final int MAX_ARRAY_SIZE = 100000;
public static final int MAX_ELEMENT_SIZE = 1000;
public static final int SORTED_STEP_SIZE = 10;
/**
* Entry point.
*/
public static void main(String[] args) {
System.out.println("Checking merge algorithm:");
MergeSorter<Integer> sorter = new MergeSorter<Integer>();
if (!checkMerge()) {
System.out.println("Failure.");
} else {
System.out.println("Success!");
}
System.out.println();
if (sortIntegers()) {
System.out.println("Integer array sort successful.");
} else {
System.out.println("Integer array sort unsuccessful.");
}
System.out.println();
System.out.println("Simple string sort:");
List<String> starray = new ArrayList<String>();
starray.add("the");
starray.add("quick");
starray.add("brown");
starray.add("fox");
starray.add("jumps");
starray.add("over");
starray.add("the");
starray.add("lazy");
starray.add("dog");
MergeSorter<String> stringsorter = new MergeSorter<String>();
stringsorter.printCollection(starray);
starray = stringsorter.sort(starray);
stringsorter.printCollection(starray);
System.out.println();
if (sortStrings()) {
System.out.println("String array sort successful.");
} else {
System.out.println("String array sort unsuccessful.");
}
}
/**
* Test against a randomly generated array of integers.
*/
private static boolean sortIntegers() {
Random rand = new Random();
int arraySize = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
List<Integer> array = new ArrayList<Integer>();
for (int i = 0; i < arraySize; i++) {
array.add(rand.nextInt(MAX_ELEMENT_SIZE));
}
SortTester<Integer> intTester = new SortTester<Integer>();
System.out.println("Initial (int) array of size " + array.size()
+ " is sorted: " + intTester.checkSorted(array));
long startTime;
long endTime;
MergeSorter<Integer> intsorter = new MergeSorter<Integer>();
startTime = System.nanoTime();
array = intsorter.sort(array);
endTime = System.nanoTime();
long mergeSortTime = endTime - startTime;
double millis = mergeSortTime / 1000000.;
System.out.println("Mergesort: " + millis + " ms");
if (millis > 500) {
System.out.println("Sort too slow, you sure it's mergesort?");
return false;
}
return intTester.checkSorted(array);
}
private static ArrayList<String> readDictionary() {
Scanner fileScan = null;
try {
fileScan = new Scanner(new File(DICTIONARY_FILE));
} catch (FileNotFoundException e) {
System.out.println("Can't find dictionary file.");
System.out.println("Modify the variable 'DICTIONARY_FILE' in SortTester.java");
System.out.println("to point to the correct file (dictionary.txt)");
System.exit(1);
}
ArrayList<String> dictionary = new ArrayList<String>(130000);
while (fileScan.hasNext()) {
dictionary.add(fileScan.next());
}
return dictionary;
}
private static boolean sortStrings() {
ArrayList<String> dictionary = readDictionary();
Random rand = new Random();
int arraySize = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
List<String> array = new ArrayList<String>();
for (int i = 0; i < arraySize; i++) {
array.add(dictionary.get(rand.nextInt(dictionary.size())));
}
SortTester<String> stringTester = new SortTester<String>();
System.out.println("Initial (String) array of size " + array.size()
+ " is sorted: " + stringTester.checkSorted(array));
long startTime;
long endTime;
MergeSorter<String> stringsorter = new MergeSorter<String>();
startTime = System.nanoTime();
array = stringsorter.sort(array);
endTime = System.nanoTime();
long mergeSortTime = endTime - startTime;
double millis = mergeSortTime / 1000000.;
System.out.println("Mergesort: " + millis + " ms");
if (millis > 500) {
System.out.println("Sort too slow, you sure it's mergesort?");
return false;
}
return stringTester.checkSorted(array);
}
/**
* Checks if an ArrayList is sorted in ascending order.
* @param array The array to verify.
* @return True if the array is sorted, false otherwise
*/
public boolean checkSorted(List<E> array) {
for (int i = 1; i < array.size(); i ++) {
if (array.get(i).compareTo(array.get(i - 1)) < 0) {
return false;
}
}
return true;
}
public static boolean checkMerge() {
// Generate two arbitrary arrays
Random rand = new Random();
int arr1Size = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
int arr2Size = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
ArrayList<Integer> arr1 = generateSortedArray(arr1Size);
ArrayList<Integer> arr2 = generateSortedArray(arr1Size);
MergeSorter<Integer> intMerger = new MergeSorter<Integer>();
ArrayList<Integer> merged = intMerger.merge(arr1, arr2);
SortTester<Integer> intTester = new SortTester<Integer>();
return intTester.checkSorted(merged);
}
public static ArrayList<Integer> generateSortedArray(int size) {
ArrayList<Integer> arr = new ArrayList<Integer>();
Random rand = new Random();
Integer prevElement = 0;
for (int i = 0; i < size; i++) {
Integer newElement = prevElement + rand.nextInt(SORTED_STEP_SIZE);
arr.add(newElement);
prevElement = newElement;
}
return arr;
}
}