Top K proeblem and the Kth big

Kth_big.py

# Udacity, CS215, Homework 4.2
# Given a list of numbers, L, find a number, x, that
# minimizes the sum of the absolute value of the difference
# between each element in L and x: SUM_{i=0}^{n-1} |L[i] - x|
# 
# Your code should run in Theta(n) time
# Why median? http://www.udacity.com/wiki/CS215Unit4SolutionsMean?course=cs215
# Modified from: http://forums.udacity.com/cs215/questions/3447/ps4-2-error-running-code-is-there-a-case-im-missing

import random

def minimize_absolute(L):
    x = Kth_big(L, 1+len(L)/2)
    return x

def partition(L, v):
    left = []
    right = []
    same = []
    for val in L:
        if val < v: left.append(val)
        if val == v: same.append(val)
        if val > v: right.append(val)
    return left, same, right

def Kth_big(L, k):
    v = L[random.randrange(len(L))]
    left, same, right = partition(L,v)
    print left, same, right
    #if len(left) == k: #wasted so much time here!
        #return left    #major difference from the top k code.
    if len(left) + len(same) == k:
        return v
    if (len(left) < k) and (len(left) + len(same) > k):
        return v
    if len(left) >= k: #len(left) == k is done here.
        return Kth_big(left, k)
    return Kth_big(right,  k-len(left)-len(same))

Print_results.py

L1 = [1,2,3,4,5,6,5,2]
L2 = [5,4,5,6]
print sorted(L1)
print minimize_absolute(L1)
print ''
print sorted(L2)
print minimize_absolute(L2)

[1, 2, 2, 3, 4, 5, 5, 6]
[] [1] [2, 3, 4, 5, 6, 5, 2]
[2, 3, 4, 2] [5, 5] [6]
[] [2, 2] [3, 4]
[] [3] [4]
[] [4] []
4

[4, 5, 5, 6]
[5, 4, 5] [6] []
[] [4] [5, 5]
[] [5, 5] []
5

top_k.py

# Udacity, CS215, 3.16-3.18 Top K Code
# The original version: http://www.udacity.com/wiki/CS215Unit4?course=cs215
# No equal elements in the list

import random

L = [31, 45, 91, 51, 66, 82, 28, 33, 11, 89, 27, 36]

def partition(L, v):
    smaller = []
    bigger = []
    for val in L:
        if val < v: smaller += [val]
        if val > v: bigger += [val]
    return (smaller, [v], bigger)

print partition(L, 84)
# >>>[31, 45, 51, 66, 82, 28, 33, 11, 27, 36, 84, 91, 89]

def top_k(L, k):
    v = L[random.randrange(len(L))]
    (left, middle, right) = partition(L, v)
    # middle used below (in place of [v]) for clarity
    if len(left) == k:   return left
    if len(left)+1 == k: return left + middle
    if len(left) > k:    return top_k(left, k)
    return left + middle + top_k(right, k - len(left) - len(middle))

print top_k(L, 5)
# >>> [31, 28, 33, 11, 27]
# list order may vary due to random selection of v


# Modified version of Top K Code 
# Consider the equal elements in the list.

import random

def partition(L, p):
    return [l for l in L if l<p], [l for l in L if l==p], [l for l in L if l>p]

def top_k(L, k):
    p = L[random.randrange(len(L))]
    left, same, right = partition(L, p)
    #print left, same, right
    if len(left) == k:
        return left
    if len(left) + len(same) == k:
        return left + same
    if len(left) < k and (len(left) + len(same)) > k:
        return left + [p]*(k - len(left))
    if len(left) > k:
        return top_k(left, k)
    return left + same + top_k(right, k-len(left)-len(same))