median.py

# Title: Randomized Algorithm (Median)
# Authors: Clay McLeod
# Description: A randomized algorithm for finding the median of an array.
# Section: Python
# Subsection: Interesting Problems

import sys
import math
import random

DOMAIN          = xrange(100000)    # Domain: 0 - 100,000
NUM_ELEMENTS    = 10000             # Number of elements: 10,000 

def find_median_randomized(S):
    """---------------------------------------------------------------------
> Documentation

Author:      Clay McLeod
Course:      CSCI 691
Date:        March 2, 2015
Assignment:  1
Description: Randomized algorithm to find the median of an array.
Input:       1) A set S of n elements over an ordered domain.
Output:      1) The median element of S
---------------------------------------------------------------------
    """
    # S is a list, has at least 1 element
    assert (isinstance(S, list) and len(S) > 0)

    # Each element is an integer
    for num in S:
        assert isinstance(num, int)

    # Set n to length of set S
    n = len(S)

    # Randomize input
    random.shuffle(S)

    # Sample n^(3/4) elements
    number_of_samples = int(math.ceil(n ** (3.0 / 4.0)))
    R = random.sample(S, number_of_samples)

    # Sort R
    R.sort()

    # Compute d as int(math.floor(((n^(3/4))/2) - math.sqrt(n)))
    d_index = int(math.floor(((n ** (3.0 / 4.0)) / 2.0) - math.sqrt(n)))
    d = R[d_index]

    # Compute u as int(math.ceil(((n^(3/4))/2) + math.sqrt(n)))
    u_index = int(math.ceil(((n ** (3.0 / 4.0)) / 2.0) + math.sqrt(n)))
    u = R[u_index]

    # Computer C, ld, and lu according to algorithm
    c = [x for x in S if d <= x and x <= u]
    ld = len([x for x in S if x < d])
    lu = len([x for x in S if x > u])

    # Assert that ld <= (n/2) and lu <= (n/2), else fail
    assert not (ld > (n / 2) or lu > (n / 2))

    # Assert that |c| <= 4*n^(3/4), else fail
    assert len(c) <= 4.0 * (n ** (3.0 / 4.0))

    # Sort C
    c.sort()

    # Return (math.floor(n/2) - ld + 1)-th element in C
    median_index = int(math.floor(n / 2) - ld + 1)
    return c[median_index]

if __name__ == "__main__":

    # print documentation
    print find_median_randomized.__doc__

    random_input = random.sample(DOMAIN, NUM_ELEMENTS)
    print 'Median: %s ' % find_median_randomized(random_input)