2
\$\begingroup\$

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.

\$\endgroup\$

migrated from superuser.com Sep 27 '12 at 8:42

This question came from our site for computer enthusiasts and power users.

  • \$\begingroup\$ It will not be O(n), it will be O(n^2). For each of the n entries, the inner while loop will iterate some number of times that scales with n. So the algortihm has an O(n) loop inside an O(n) loop, making it O(n^2). You need to heavily optimize the number of compares you do in the inner loop. Why are you skipping by only 1 every time? (Also, make sure you use a data structure whose insert operation is O(1) or that will be a problem too.) \$\endgroup\$ – David Schwartz Sep 27 '12 at 7:03
  • \$\begingroup\$ yes that is true, however that is what i am trying to solve, the 2nd part is there only because it works - even if slow, and i cant think of a better way to do it for the life of me, i would like to replace it with something that would not have to do the other loops if at all possible. any ideas? \$\endgroup\$ – Scott C Sep 27 '12 at 7:13
  • \$\begingroup\$ Have you read en.wikipedia.org/wiki/Sorting_algorithm ? \$\endgroup\$ – Colin 't Hart Sep 27 '12 at 8:08
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$
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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy