radix sort

ひまつぶし

def maxof(xs, fn):
    ma = fn(xs[0])
    for x in xs:
        tmp = fn(x)
        if ma < tmp:
            ma = tmp
    return tmp

def radix_sort(xs, M):
    bs = [[] for i in range(M)]
    N = maxof(xs, len)
    checks = [0 for _ in range(M)]
    for x in xs:
        bs[int(x[-1])].append(x)

    for i in range(2, N+1):
        for k in range(M):
            checks[k] = 0
        for j, b in enumerate(bs):
            for _ in range(checks[j], len(b)):
                x = b.pop(0)
                k = int(x[-i])
                bs[k].append(x)
                checks[k] += 1
    return bs

if __name__ == "__main__":
    import random
    xs = [str(random.randint(100, 990)) for i in range(200)]
    print [x for xs in radix_sort(xs, 10) for x in xs]

"""
['101', '112', '113', '118', '119', '124', '128', '133', '136', '137', '140', '147', '152', '154', '159', '164', '167', '169', '178', '179', '186', '191', '193', '193', '196', '220', '223', '224', '233', '234', '244', '246', '247', '247', '256', '264', '266', '273', '280', '288', '288', '290', '297', '300', '301', '302', '308', '313', '323', '340', '346', '348', '350', '350', '355', '367', '368', '375', '376', '386', '387', '396', '400', '405', '407', '414', '416', '420', '426', '431', '436', '439', '441', '445', '445', '445', '446', '453', '455', '459', '461', '473', '498', '501', '515', '517', '522', '529', '531', '540', '541', '542', '544', '545', '546', '563', '566', '573', '573', '574', '576', '577', '588', '588', '591', '595', '598', '599', '605', '606', '612', '616', '624', '625', '626', '638', '640', '644', '660', '663', '665', '668', '673', '676', '677', '680', '683', '688', '689', '690', '693', '694', '696', '697', '699', '699', '704', '705', '710', '719', '719', '724', '733', '735', '742', '742', '753', '781', '782', '785', '786', '787', '792', '796', '802', '806', '807', '808', '813', '814', '817', '822', '824', '829', '835', '836', '836', '840', '840', '843', '845', '852', '859', '859', '863', '891', '891', '893', '893', '895', '895', '897', '902', '903', '910', '912', '914', '916', '916', '925', '926', '939', '945', '956', '956', '962', '963', '968', '969', '986']
"""