Counting Sort

def counting(lst):
    #For some reason hash(-1) = -2, the rest makes sence.
    if lst:
        smallest = lst[0].__hash__()
        largest = lst[0].__hash__()
    else:
        smallest = 0
        largest = 0
    for x in lst:
        x = x.__hash__()
        if x > largest:
            largest = x
        if x < smallest:
            smallest = x
    mapping = []
    for x in range(smallest, largest + 1):
        mapping.append(0)
    for x in lst:
        x = x.__hash__()
        mapping[x - smallest] += 1
    print smallest
    print mapping
    for x in range(len(mapping) - 1):
        mapping[x + 1] += mapping[x]
    oldlist = lst[:]
    for x in oldlist:
        lst[mapping[x.__hash__() - smallest] - 1] = x
        mapping[x.__hash__() - smallest] -= 1
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s