median.py

def partition(data, lo, hi):
    pivot = data[lo]
    print 'part', lo, hi, pivot
    i, j = lo + 1, hi - 1
    while True:
        while data[i] <= pivot:
            i = i + 1
            if i == hi:
                break
        while data[j] > pivot:
            j = j - 1
            if j == lo:
                break
        if i >= j:
            break
        data[i], data[j] = data[j], data[i]
    data[lo], data[j] = data[j], data[lo]
    print 'parition done', data[j], j, data
    return j

    for i in range(lo, hi):
        if data[i] < pivot:
            data.insert(lo, data.pop(i))
    print pivot, lo, hi, pivot, data.index(pivot), data
    return data.index(pivot)

def quicksort(data, lo, hi):
    if hi - lo <= 1:
        return
    index = partition(data, lo, hi)
    print 'DONE', index, lo, hi
    quicksort(data, lo, index)
    quicksort(data, index + 1, hi)

def median(data):
    quicksort(data, 0, len(data))
    middle = len(data) / 2
    print 'middle', middle
    if len(data) % 2 == 0:
        print 'even', data[middle - 1], data[middle]
        return (float(data[middle - 1]) + float(data[middle])) / 2
    else:
        return data[middle]

data = [62, 48, 81, 48, 44, 79, 48, 52, 55, 72, 43, 71, 51]
#data = ['K', 'R', 'A', 'T', 'E', 'L', 'E', 'P', 'U', 'I', 'M', 'Q', 'C', 'X', 'O', 'S']
print median(data)

test_median.py

import random
import unittest
import median

data = [
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
]

class MedianTest(unittest.TestCase):
  def test_median(self):
      random.shuffle(data)          
      print data
      self.assertEqual(median.median(data), 5)

if __name__ == '__main__':
  unittest.main()