Sorting Comparisons Preface
For this lab, you will implement the five sorting algorithms we discussed (selection, bubble, insertion, merge, quick), and compare their runtime performance.
Requirements
- Create a class called SortingComparison.
- In that class, create five static methods, one for each algorithm that sorts an array of a generic type, using this header format:
? public static > E[] algName(E[] arrayToSort)
? Each algorithm takes in an array of items of a generic type E (which may or may not be sorted), and returns an array that has the items sorted from smallest to largest.
- You may, and should, create private helper methods for some sorting algorithms.
- Write additional functionality that does the following.
? Creates 1,000 arrays that each hold 100,000 items that are randomly generated.
? Passes each of the 1,000 arrays to each sorting algorithm method.
? Measures how long it takes each call to a sorting algorithm method to complete.
? Calculates the average time for each sorting method to sort the 1,000 arrays.
? Prints the average time for each sorting method to the console.
Hints
- Use System.nanoTime() to calculate how long it takes a sorting method to complete.
- For example:
? Integer[] arrayToSort; // build a random array to sort.
? long beginTime = System.nanoTime();
? insertionSort(arrayToSort);
? long endTime = System.nanoTime();
? long elapsedTime = endTime - beginTime;
? // elapsedTime contains how long it took insertionSort to complete.
- You can search for, find, copy, and adapt existing sorting implementations.