In this lab you are asked to implement three different algorithms for median finding, or more generally for selection of the k'th smallest element in an unordered array. You will then be asked to compare these algorithms.
The three algorithms have the same input and output:
This is the algorithm we cover in class. It is described in Section 2.4 of the textbook.
Although the randomized selection algorithm runs in time O(n) in expectation, it is actually possible to design a deterministic algorithm for selection which also runs in time O(n). The main difference between the deterministic selection algorithm and the randomized selection algorithm in Section 2.4 of the textbook is how to choose the pivot. In Algorithm 2, divide A into groups of 5 elements (except the last group), then compute the medians M[1,..,n/5] of these groups using sorting (which takes O(1) per group), then use the selection algorithm recursively to compute the median of M[1,..,n/5] and use this value as the pivot to divide A into Sl, Sv, and Sr as before. When the size of input A is not too large (e.g., no more than 10) you are allowed to use any sorting algorithm (quicksort, mergesort, bubblesort, etc.) In you need more details, feel free to look at the following Lecture Notes.
Implement Quicksort (page 56 of textbook), then use it to sort A, and return the k'th smallest element. Note that most of the code for Quicksort should be very similar to your Algorithm 1. Quicksort runs in expected O(n log n) time.