Finding kth maximum in O(n) average time

December 17, 2010 at 11:39 pm (Uncategorized)

The algorithm is as follows (taken from

function select(list, left, right, k)
     select pivotIndex between left and right
     pivotNewIndex := partition(list, left, right, pivotIndex)
     if k = pivotNewIndex
         return list[k]
     else if k < pivotNewIndex
         return select(list, left, pivotNewIndex-1, k)
         return select(list, pivotNewIndex+1, right, k)

Here is the Python code that implements the function and also tests the function with random inputs.

The partition function itself is not as efficient as possible. It can be done in O(n) space as well, whereas we currently create new sub-lists.

import random
def kthmax (array, k):
    pivot = array [ len(array) - 1]
    # partition
    lesser = filter (lambda x: x < pivot, array[ :len(array) -1 ])
    pivot_position = len(lesser) + 1
    greater = filter (lambda x: x >= pivot, array[ :len(array) - 1 ])
    # partition done
    if (pivot_position == k):
        return pivot
    elif (pivot_position > k):
        return kthmax (lesser, k)
    elif (pivot_position < k):
        return kthmax (greater, k - pivot_position)

for i in range(1000):
    loopLimit = random.randint (1,1000)
    randomArray = []
    for i in range(loopLimit):
    kth = random.randint (1, loopLimit - 1)
    result = kthmax (randomArray, kth)

    if ( randomArray[kth - 1] == result ):
        print "pass"
        print "FAIL"

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: