14. Sorting Recursively
Feel free to use your laptop
You are strongly encourage to work with others
When you get stuck, ask those sitting around you for help
Get used to working together in the labs
Peer teaching and peer learning has been empirically shown to be very effective
14.1. Starting Point
This lab focuses on the sorting algorithms discussed in the Sorting Recursively Topic
Unlike the previous lab, an
IndexedBagis usedThe below code can be used for setting up an array to be sorted
This code can also be used for timing the different sorting algorithms
public static void main(String[] args){
IndexedBag<Integer> toSort = createUnsortedIntBag(10000, 10);
System.out.println(toSort);
double startTime = System.nanoTime();
//quicksort(toSort);
//mergesort(toSort);
double endTime = System.nanoTime();
System.out.println(toSort);
System.out.println("runtime: " + (endTime - startTime)/1000000 + " ms");
}
public static IndexedBag createUnsortedIntBag(int n, int maxValue){
IndexedBag<Integer> toSort= new ArrayIndexedBag<>(n);
for(int i = 0; i < n; ++i){
toSort.add((int)(Math.random() * maxValue));
}
return toSort;
}
14.2. Quicksort
Implement the quicksort algorithm
Make sure it works and run it a few times to see what the runtimes are
Change the size of the array and the max value and see how it impacts runtimes
For the purposes of this lab, do not worry about writing unit tests
public static <T extends Comparable<T>> void quicksort(IndexedBag<T> toSort){
// Fill me in
}
14.3. Mergesort
Implement the mergesort algorithm
Make sure it works and run it a few times to see what the runtimes are
Change the size of the array and the max value and see how it impacts runtimes
For the purposes of this lab, do not worry about writing unit tests
public static <T extends Comparable<T>> void mergesort(IndexedBag<T> toSort){
// Fill me in
}
14.4. Comparing Sorts
Run each of the sorts a few times and take note of the runtimes
Play around with the size of the lists and the max value
Compare the runtimes of each algorithm to what was expected based on their computational complexities
Compare these runtimes to the sorting algorithms implemented in the previous lab