Objective : Implement the mergesort algorithm using Java generics. Description :

Question

Objective: 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 Finally: Upload the .java file to the dropbox

Driver File:

File to Ammend:

Explanation / Answer

//Merge Sort using Java Generics public class SorterApp { public static void main(String[] args) { SorterApp app = new SorterApp(); app.run(); } private void run() { sort(new Integer[] { 2, 42, -3, 2, 4 }); sort(new Integer[] { 1, 2, 3, 4, 5 }); sort(new Integer[] { 3, 1, 5, 4, 2 }); sort(new Integer[] { 5, 4, 3, 2, 1 }); System.out.println(); sort(new String[] { "a", "b", "c", "d", "e" }); sort(new String[] { "c", "a", "e", "d", "b" }); sort(new String[] { "e", "d", "c", "b", "a" }); } private void sort(T[] values) { Sortable sorter = newSortable(5); sorter.sortAscending(values); // sorter.sortDescending(values); Utils.printArray(values); } private Sortable newSortable(int sortableAlgorithm) { switch (sortableAlgorithm) { case 1: return new BubbleSort(); case 2: return new InsertionSort(); case 3: return new SelectionSort(); case 4: return new CountingSort(); case 5: return new MergeSort(); default: return new BubbleSort(); } } } public class SelectionSort extends Sorter implements Sortable { private int count = 0; @Override public void sortAscending(T[] values) { count = 0; mergeSort(values, 0, values.length - 1, 0); System.out.printf("%2s: ", count); } @Override public void sortDescending(T[] values) { count = 0; mergeSort(values, 0, values.length - 1, 1); System.out.printf("%2s: ", count); } public static List newList(int initialCapacity) { return new ArrayList(initialCapacity); } private void mergeSort(T[] arValues, int low, int high, int orderType) { if (low

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---