creating a hash based sorting algorithm

Question

For experimental and learning purposes. I was trying to create a sorting algorithm from a hash function that gives a value biased on alphabetical sequence of the string, it then would ideally place it in the right place from that hash.

The reasoning is that theoretically if done right this algorithm can achieve O(n) speeds or nearly so.

So here is what I have worked out in python so far:

letters = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,
'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,
's':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25,
'A':0,'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,
'K':10,'L':11,'M':12,'N':13,'O':14,'P':15,'Q':16,'R':17,
'S':18,'T':19,'U':20,'V':21,'W':22,'X':23,'Y':24,'Z':25}    

def sortlist(listToSort):
    listLen = len(listToSort)
    newlist = []
    for i in listToSort:
        k = letters[i[0]]
        for j in i[1:]:
            k = (k*26) + letters[j]
        norm = k/pow(26,len(i)) # get a float hash that is normalized(i think thats what     it is called)

        # 2nd part
        idx = int(norm*len(newlist)) # get a general of where it should go
        if newlist: #find the right place from idx
            if norm < newlist[idx][1]:
                while norm < newlist[idx][1] and idx > 0: idx -= 1
                if norm > newlist[idx][1]: idx += 1
            else:
                while norm > newlist[idx][1] and idx < (len(newlist)-1): idx += 1
                if norm > newlist[idx][1]: idx += 1
        newlist.insert(idx,[i,norm])# put it in the right place with the "norm" to ref     later when sorting
    return newlist

I think that the 1st part is good, but the 2nd part needs help. so the Qs would be what would be the best way to do something like this or is it even possible to get O(n) time (or near that) out of this?

The testing I did with an 88,000 word list took prob about 5 min, 10,000 took about 30 sec it got a lot worse as the list count went up.

If this idea actually works out then I would recode it in C to get some real speed and optimizations.

Thank for any advice that you could give.

Answer 1

You have reinvented a form of radix sort. See that page for how to get rid of the two nested O(n) loops.

It is possible to get O(n) if the maximum length of the words to be sorted is assumed to be a constant.

Answer 2

letters = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,
'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,
's':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25,
'A':0,'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,
'K':10,'L':11,'M':12,'N':13,'O':14,'P':15,'Q':16,'R':17,
'S':18,'T':19,'U':20,'V':21,'W':22,'X':23,'Y':24,'Z':25}    

Python convention says that constants should be named in ALL_CAPS. I'd also suggest writing code to build this dict from string.ascii_lowercase

def sortlist(listToSort):

Use _ to seperate words in function/parameter names, this line should be: def sort_list(list_to_sort): to follow python guidelines.

    listLen = len(listToSort)

I don't see that you ever use this

    newlist = []
    for i in listToSort:
        k = letters[i[0]]
        for j in i[1:]:
            k = (k*26) + letters[j]

Set k=0 before the loop, and then you won't need to slice the string.

        norm = k/pow(26,len(i)) # get a float hash that is normalized(i think thats what     it is called)

a norm has a specific meaning, instead, I'd call this normalized.

        # 2nd part
        idx = int(norm*len(newlist)) # get a general of where it should go

The problem is that this assumes you'll have a pretty even distribution of all possible strings. That's never going to happen, since some letters are used far less then others. This simple isn't going to be a good heuristic.

        if newlist: #find the right place from idx
            if norm < newlist[idx][1]:
                while norm < newlist[idx][1] and idx > 0: idx -= 1
                if norm > newlist[idx][1]: idx += 1
            else:
                while norm > newlist[idx][1] and idx < (len(newlist)-1): idx += 1
                if norm > newlist[idx][1]: idx += 1

This is going to rather slowly move to the correct position. Finding the correct position would be much better done by using binary search. The bisect module has functions to do it.

        newlist.insert(idx,[i,norm])# put it in the right place with the "norm" to ref     later when sorting

This line will kill your performance. The insert is going to have to move items around constantly. That'll make your algorithm O(n^2).

    return newlist

See the radix or bucket sort, they are getting at the same ideas you are.