Implement a linear-expected-time algorithm for selecting the kth smallest element
Algorithm description
1. If |S| = 1, then k = 1 and return the element in S as the answer.
2. Pick a pivot element, v[S]. Partition S-{v} into S1 and S2, as done with quicksort
3. If k<=|S1|, then the kth smallest element must be in S1. In this case, return quickselect(S1,k).
4. If k=1+|S1|, the pivot is the kth smallest element and return it.
5. Otherwise, the kth smallest element lies in S2, and it is the (k-|
S1|-1)st smallest element in S2, and return quickselect(S2,k-| S1|-1).
Deliverables
1. Source code, i.e. *.java file
2. Time complexity analysis