Hands-On Data Structures and Algorithms with Python - Second Edition

Quick select

The quickselect algorithm is used to obtain the k^th smallest element in an unordered list of items, and is based on the quicksort algorithm. In quicksort, we recursively sort the elements of both the sublists from the pivot point. In quicksort, in each iteration, we know that the pivot value reaches its correct position in the list with two sublists (left and right sublists), having all of their elements set to be unordered.

However, in the case of the quickselect algorithm, we recursively call the function exclusively for the sublist that has the k^th smallest element. In the quickselect algorithm, we compare the index of the pivot point with the k value to obtain the k^th smallest element from the given unordered list. There ...