CODEWITHSUNDEEP
pythonlistsorting
Nili Sabbah
Nili Sabbah

Reputation: 33

Sorting a list using an alphabet string

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.

Upvotes: 1

Views: 237

Answers (1)

njzk2
njzk2

Reputation: 39406

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)

Upvotes: 3

Related Questions