Right after learning the Quicksort Algorithm in one of my algorithms classes we learned the **Quickselect Algorithm**. The Quickselect Algorithm is a selection algorithm, whereas the Quicksort Algorithm is a sorting algorithm. The really interesting part about the Quickselect Algorithm is that it is essentially the Quicksort Algorithm, except that one only needs to recursively call only one side of the partition to be re-partitioned. This changes the best case runtime from O(nlogn) to O(n).

Let me back up a second and re-establish the problem the Quickselect Algorithm solves. The problem is that we have an unordered list of items and want to find the k-th smallest item. We know we can find the item easily by sorting it first, which will take O(nlogn) to sort the list and then O(1) to find it. If you will need to do many k-th item lookups you may be better off just sorting the list, caching it, and then performing many O(1) lookups.

However, if this is not the case, the Quickselect Algorithm will find the kth-smallest item in an unordered list with a best case runtime of O(n). The code is almost identical to the Quicksort Algorithm in Python, except we are only recursively partitioning one side of the list and a few other minor differences. I re-wrote the Quicksort Algorithm in Python from scratch again, and then modified it a bit to make it the Quickselect Algorithm in Python.

Here is example code for the Quickselect Algorithm in Python.

def quickselect(items, item_index): def select(lst, l, r, index): # base case if r == l: return lst[l] # choose random pivot pivot_index = random.randint(l, r) # move pivot to beginning of list lst[l], lst[pivot_index] = lst[pivot_index], lst[l] # partition i = l for j in xrange(l+1, r+1): if lst[j] < lst[l]: i += 1 lst[i], lst[j] = lst[j], lst[i] # move pivot to correct location lst[i], lst[l] = lst[l], lst[i] # recursively partition one side only if index == i: return lst[i] elif index < i: return select(lst, l, i-1, index) else: return select(lst, i+1, r, index) if items is None or len(items) < 1: return None if item_index < 0 or item_index > len(items) - 1: raise IndexError() return select(items, 0, len(items) - 1, item_index)

Here is a short Python Script to test the Quickselect Algorithm.

a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] for i in xrange(0, len(a)): print '{0:2} found in position {1}.'.format(i, quickselect(a, i)) 0 found in position 0. 1 found in position 1. 2 found in position 2. 3 found in position 3. 4 found in position 4. 5 found in position 5. 6 found in position 6. 7 found in position 7. 8 found in position 8. 9 found in position 9. 10 found in position 10.

Note: I keep forgetting to post these solutions using Python 3.5. I am using both Python 2.7 and 3.5 during my learning so I can better understand the differences and program in both. Minor changes need to be done to get this to work in Python 3.5. Change `xrange`

to `range`

and, of course, modify the `print`

statements.

Best Wishes!

**Posted by David Hayden**