Setup
Register for the lab using http://register.caltech.codes/ and clone the repository as explained in the setup instructions.
Goals and Outcomes
In this lab, you will implement insertion sort and “break” quicksort!
By the end of this lab, you will…
- be more familiar with basic sorting algorithms
- have some experience with asymptotic analysis
Insertion Sort
Insertion sort is one of the simplest sorting algorithms. It has an average time complexity of \(\Theta(n^2)\) and a best-case time complexity of \(\Theta(n)\) when the list is already sorted. Insertion sort is explained in more detail on slide 5 of the sorting lecture.
Task 0.
Implement insertion sort in InsertionSort.java. You should modify the input array in-place.
Hint:
- If you are getting an error like “Operator ‘>’ cannot be applied to ‘E’, ‘E’”, it is because the generic type
Edoesn’t necessarily have comparison operators such as “>” and “<” implemented. Instead, you should use thecompareTo()method to make comparisons.
Quick Sort
Quick sort is a “fancier” sorting algorithm with an average time complexity of \(\Theta(n\log(n))\). However, it has a weakness! When the pivots are chosen poorly, it has a time complexity of \(\Omega(n^2)\). Quick sort (and an idea about how to break it) is explained in more detail on slide 13 of the sorting lecture.
Given a target array length n, your job is to generate an array of length n which makes our implementation of quick sort have \(\Omega(n^2)\) time complexity. Our implementation selects an element at the middle of the array to be the pivot. One way to think about how to do this is to draw out the swaps quick sort performs in its worst case scenario to arrive at a sorted array. Your algorithm should work backwards and perform these swaps in reverse when generating your own array.
Breaking Quick Sort
Quick sort performs at its worst when the pivot doesn’t divide up the remaining items in the array - for example when the pivot is the maximum or minimum value in the array.
Exploring the worst-case scenario
Let’s imagine we have an array of length 5 which is ordered in a way that causes quicksort to always choose a pivot which is the maximum value of the remaining items to be sorted.
[a, b, c, d, e, f]
Our implementation of quick sort chooses the middle element for the pivot, which is c in this case (because we choose the earlier element if there is no exact middle element). No other swaps are performed because, in the worst-case scenario, every single other element is checked against c and ends up being smaller than it. After this step, our array looks like this:
[a, b, f, d, e, c]
We will choose the middle element of the remaining unsorted elements in indexes 0-4, which is f. Again, we are imagining the worst-case scenario, so f will be the largest element of the remaining elements to be sorted. Now, we have:
[a, b, e, d, f, c]
We repeat this process with b as our pivot. Again, it is the largest element of the remaining elements.
[a, d, e, b, f, c]
Same idea with d as our pivot now.
[a, e, d, b, f, c]
Now with a.
[e, a, d, b, f, c]
Notice that we had to choose n-1 pivots, and each pivot involved moving roughly half of the remaining unsorted elements each time. With some math, we can indeed prove that this case has \(\Theta(n^2)\) time complexity.
Finding an algorithm
Since the list [e, a, d, b, f, c] is now sorted, let’s subsitute all of the variables for numbers so we can think about the algorithm we want to develop more concretely. Thus, we can let e=1, a=2, d=3, b=4, f=5, and c=6. Therefore, the process quick sort actually just performed looks like this:
[2, 4, 6, 3, 1, 5]
[2, 4, 5, 3, 1, 6]
[2, 4, 1, 3, 5, 6]
[2, 3, 1, 4, 5, 6]
[2, 1, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
Task 1.
Complete genArray in QuickSortBreaker.java. You can either come up with an algorithm to generate the adversarial array directly, or start with a sorted list and do a “reverse quick sort.” Either way, for a six element list of integers, you should end up generating an array that looks like [2, 4, 6, 3, 1, 5].
Checking the Results on gitlab
Task 2. Check to make sure you are passing all the tests on gitlab.