Finding kth maximum in O(n) average time

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

The algorithm is as follows (taken from http://en.wikipedia.org/wiki/Selection_algorithm):

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)
     else
         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.

#!/usr/bin/python 
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):
        randomArray.append(i)
    kth = random.randint (1, loopLimit - 1)
    result = kthmax (randomArray, kth)

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: