Objectives:

• Examine the implementation of different sorts
• Evaluate the performance difference between different sorts

Activity

Create and clone this GitHub Classroom repository: classroom.github.com/g/YBglCT48. This is the same repository as the "big-O" lab with some minor improvements. The code now includes four methods for generating arrays:

• randomIntArray: Generate an array containing primitive Java ints in random order.
• randomIntegerArray: Generate an array containing Java Integer wrapper objects in random order.
• orderedIntArray: Generate an array containing primitive Java ints in ascending order.
• orderedIntegerArray: Generate an array containing Java Integer wrapper objects in ascending order.

Be sure to take note of the difference between the "*IntArray" and "*IntegerArray" methods. You will need the "Integer" versions for methods that use generics.

1. Implement a selection sort.
2. Predict whether your selection sort will run faster when the input array is already sorted? Why or why not? If faster, will it be the same complexity class (i.e., same "big-O")?
3. Use the measureRunningTime method from the "big-O" lab to measure the running time of your selection sort using arrays of random values.
4. Now measure the running time of your selection sort using an array of already sorted values as input. (In other words, see how long it takes to "sort" an already-sorted list.)
5. Was your prediction from #2 correct?
6. Implement an insertion sort.
7. Will your insertion sort run faster if the input array is already sorted? Why or why not? If faster, will it be the same complexity class (i.e., same "big-O")?
8. Measure the running time of your insertion sort using an array of random values as input.
9. Measure the running time of your insertion sort using an array of already sorted values as input.
10. Was your prediction from #7 correct?
11. Implement a merge sort.
12. Implement a quick sort.
13. Measure and compare the running time of mergesort and quicksort. (Present your findings as "speedup": mergesort_time/quicksort_time.)
14. Do mergesort and quicksort appear to have the same big-O? If not:
    • Explain why your implementation of mergesort does not have the expected big-O.
    • Fix the code.
15. Measure and compare the running time of your quicksort with that of the algorithm used by Arrays.sort. (Present your findings as "speedup": your_quicksort_time/Arrays.sort_time.)
16. How large of an array can you sort in one minute using a selection sort?
17. How large of an array can you sort in one minute using quicksort?
18. Implement one of your sorts using the Comparator design discussed in Section 18.4

Submission

Updated Wednesday, 8 July 2020, 6:31 PM