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)
            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 Koder Dojo

Hi, and welcome to Koder Dojo! I am a freelance, C# ASP.NET MVC Developer learning Python as well as topics on computer science, data structures, and algorithms. This website is a daily journal of my learnings, and I hope the code samples and topics help and inspire you as a developer. I am very interested in meeting others interested in similar subjects, so please connect with me on twitter. I am @KoderDojo.

Related Posts: