Sorting a list using an alphabet string

Question

I'm trying to sort a list containing only lower case letters by using the string :

alphabet = "abcdefghijklmnopqrstuvwxyz".

that is without using sort, and with O(n) complexity only. I got here:

def sort_char_list(lst):
alphabet = "abcdefghijklmnopqrstuvwxyz"
new_list = []
length = len(lst)

for i in range(length):
    new_list.insert(alphabet.index(lst[i]),lst[i])
    print (new_list)

return new_list

for this input :

m = list("emabrgtjh")

I get this:

['e']
['e', 'm']
['a', 'e', 'm']
['a', 'b', 'e', 'm']
['a', 'b', 'e', 'm', 'r']
['a', 'b', 'e', 'm', 'r', 'g']
['a', 'b', 'e', 'm', 'r', 'g', 't']
['a', 'b', 'e', 'm', 'r', 'g', 't', 'j']
['a', 'b', 'e', 'm', 'r', 'g', 't', 'h', 'j']
['a', 'b', 'e', 'm', 'r', 'g', 't', 'h', 'j']

looks like something goes wrong along the way, and I can't seem to understand why.. if anyone can please enlighten me that would be great.

You're inserting into your new_list at the index of your alphabet string... this won't sort your list. — xnx
– xnx, Commented Dec 9, 2014 at 20:32
Its not O(n) if you have to search the list each iteration (which is what index has to do). — Scott Hunter
– Scott Hunter, Commented Dec 9, 2014 at 20:32
why not? it looks like it's working until i=6. I would be glad if you can explain more (: — Nili Sabbah
– Nili Sabbah, Commented Dec 9, 2014 at 20:34
Try opening a python shell and writing: x = [], then x.insert(42, "foo"). You won't see "foo" in the 42nd entry of x, you'll see something else... — jme
– jme, Commented Dec 9, 2014 at 20:35

njzk2 · Accepted Answer · 2014-12-09 20:44:04Z

3

You are looking for a bucket sort. Here:

def sort_char_list(lst):
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    # Here, create the 26 buckets
    new_list = [''] * len(alphabet)

    for letter in lst:
        # This is the bucket index
        # You could use `ord(letter) - ord('a')` in this specific case, but it is not mandatory
        index = alphabet.index(letter)
        new_list[index] += letter

    # Assemble the buckets
    return ''.join(new_list)

As for complexity, since alphabet is a pre-defined fixed-size string, searching a letter in it is requires at most 26 operations, which qualifies as O(1). The overall complexity is therefore O(n)

answered Dec 9, 2014 at 20:44

njzk2

39.4k7 gold badges72 silver badges111 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Nili Sabbah Over a year ago

thank you so much, I'm so glad to learn new things and methods to deal with problems. I'm still very new to this, it is great this community exists to share great peoples' ideas. thanks again !

Collectives™ on Stack Overflow

Sorting a list using an alphabet string

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related