[Shootout-list] Python Heapsort

[Kevin Carson]

I've attached a new Python heapsort implementation.  The current one not
only doesn't return the correct value because it confuses the concept of a
Python Heap with the sorting algorithm called "Heap Sort".

Kevin

#!/usr/bin/python -OO
# $Id: heapsort-python.code,v 1.6 2005/02/10 06:14:54 bfulgham Exp $
# http://shootout.alioth.debian.org/
#
# Updated by Valentino Volonghi for Python 2.4
# Reworked by Kevin Carson to produce correct results and same intent

import sys

IM = 139968
IA =   3877
IC =  29573

LAST = 42
def gen_random(max) :
    global LAST
    LAST = (LAST * IA + IC) % IM
    return( (max * LAST) / IM )

def heapsort(n, ra) :
    ir = n
    l = (n >> 1) + 1

    while True :
        if l > 1 :
            l -= 1
            rra = ra[l]
        else :
            rra = ra[ir]
            ra[ir] = ra[1]
            ir -= 1
            if ir == 1 :
                ra[1] = rra
                return

        i = l
        j = l << 1
        while j <= ir :
            if (j < ir) and (ra[j] < ra[j + 1]) :
                j += 1

            if rra < ra[j] :
                ra[i] = ra[j]
                i = j
                j += j
            else :
                j = ir + 1;
        ra[i] = rra;

def main() :
    if len(sys.argv) == 2 :
        N = int(sys.argv[1])
    else :
        N = 1

    ary = [None]*(N + 1)
    for i in xrange(1, N + 1) :
        ary[i] = gen_random(1.0)

    heapsort(N, ary)

    print "%.10f" % ary[N]

main()