Find k-th smallest element using QuickSelect algorithm

Given an initial unsorted list of N elements, we want to quickly find the k-th smallest element. For example, for the list {7, 4, 1, 5, 6}, the first smallest is 1, second smallest is 4 and so on.

An easy approach is to sort the elements in O(N logN) and select the k-th element as our solution. But we do we really need to sort the entire list?
Quickselect is an approach where we use divide and conquer and find the k th smallest element in an average O(N) time.

Quickselect algorithm

Quickselect w...