quick sort with counting comparisons

qs.py

import sys
import logging

global log
log = logging.getLogger('qs')
log.addHandler(logging.StreamHandler())

def readFromFile(fname):
    print "reading " + fname
    txt = open(fname)
    
    li = []
    while True:
        l = txt.readline()
        if len(l) == 0:
            break # EOF
        
        li.append(long(l.rstrip()))
    txt.close()
    log.debug(">> read " + str(len(li)) + " entries from " + filename)
    return li


# tbd code below assumes there're no duplicate elements in given input

def partition(list, l, r, pivotidx):
    """im-place quicksort partitioning, returns new pivot poit"""
    pivot = list[pivotidx]
    # place pivot into first element
    list[l], list[pivotidx] = list[pivotidx], list[l]
    i = l + 1
    log.debug(">> init part " + str(list[l:r+1]) + " i " + str(i) + " pivot " + str(pivotidx) + '/' +str(pivot))
    for idx in range(l + 1, r+1):
        if list[idx] < pivot:
            list[idx], list[i] = list[i], list[idx]
            i += 1
        log.debug(">> part " + str(list[l:r+1]) + " i " + str(i) + " idx " + str(idx) + " pivot " + str(pivotidx) + '/' +str(pivot))
    # move pivot to the proper place
    log.debug( ">> swap pivot " +  str(list[l]) + " with " + str(list[i-1]) + " at i-1 " + str(i-1) )
    list[i-1], list[l] = list[l], list[i-1]
    return i - 1
 
def _qs(list, l, r, pf):
    """quick sorting"""
    cmps = 0
    if r > l:
        # pick new pivot
        pivotidx = pf(list, l, r)
        log.debug( ">> pre-part  " + str(list[l:r+1]) + " l " + str(l) + " r " + str(r) + " pivotidx " + str(pivotidx) )
        pivotidx = partition(list, l, r, pivotidx)
        log.debug( ">> post-part " + str(list[l:r+1]) + " new pivotidx " + str(pivotidx) )
        (left, cmpl)  = _qs(list, l, pivotidx -1, pf)
        (right, cmpr) = _qs(list, pivotidx + 1, r, pf)
        cmps = (r - l) + cmpl + cmpr
    # else:
    #     print "nothing to do for " + str(list[l:r+1])

    return (list, cmps)
 
def qs_inplace(mylist, pf):
    return _qs(mylist, 0, len(mylist) - 1, pf)


# really inefficient but quick to write
def find_median(list, l, r):
    fi, li, mi  = l, r, (l+r)/2
    r = [(fi, list[fi]), (li, list[li]), (mi, list[mi])]
    # feeling lazy
    r = sorted(r, key = lambda v : v[1])
    return (r[1])[0]

### test code
test_input = [[1], 
              [1,2,3], 
              [1,2,3,4], 
              [9, 6, 3, 7, 2, 4],
              [9, 6, 3, 7, 4, 2]]


def testOne(qsf, l):
    pf_first = lambda list, l, r: l
    pf_last = lambda list, l, r: r

    print "original list " + str(l)
    first = qsf(list(l), pf_first)
    last = qsf(list(l), pf_last)
    median = qsf(list(l), find_median)

    print "first  " + str(first[1]) 
    print "last   " + str(last[1])
    print "median " + str(median[1])


def testQS(qsf, lists):
   
    pf_left = lambda list, l, r: l
    pf_right = lambda list, l, r: r
    for l in lists:
        testOne(qsf, l)
        print


#log.setLevel(logging.DEBUG)    

#testOne(qs_inplace, [9, 6, 3, 7, 2, 4])

testQS(qs_inplace, test_input)

# if given file name read input from file and sort
if len(sys.argv) > 1:
    script, filename = sys.argv
    l = readFromFile(filename)
    testOne(qs_inplace, l)