sort array based on custom alphabet order python

Question

I want to write a code to sort arr based on customAl order, and not use sorted function.

customAl = [dshbanfmg]
arr = [bba,abb,baa,mggfba,mffgh......]

psudo code:

def sortCA(arr, customAl):
    dt = {}
    generate dt order based on customAl
    look up and sort arr

    return result


newArr = [bba,baa,abb,mffgh,mggfba......]

I know there's a similiar question but the answer is wrapped in sorted function which I don't wish to use. anyone has a better solution than unsorted, or dictionary which takes space?

Sorting string values according to a custom alphabet in Python

I think the solution you linked to is a good solution. It doesn't even use dictionaries. It does use a key for sorting though (that's unrelated to dictionary keys). — Alassane Ndiaye
– Alassane Ndiaye, Commented May 7, 2019 at 23:29
Possible duplicate of Sorting string values according to a custom alphabet in Python — chickity china chinese chicken
– chickity china chinese chicken, Commented May 8, 2019 at 0:51
As I stated in my post, I am not looking for answers that use sorted function. That defeats the purpose of posting this thread. — Sailormoon
– Sailormoon, Commented May 8, 2019 at 20:46
@Sailormoon Why not use sorted? Would list.sort work instead? — wjandrea
– wjandrea, Commented May 8, 2019 at 20:52
None of the names like dshbanfmg and bba are not defined in your example. Are they supposed to be strings? — wjandrea
– wjandrea, Commented May 8, 2019 at 21:01

recnac · Accepted Answer · 2019-05-09 02:49:43Z

2

In my opinion, programming is a trade-off, it depends on which part you care most.

Specifically, in this scenario, you can choose to trade time for space by str.index, or you can trade space for time with an extra index dict:

customAl = 'dshbanfmg'
arr = ['bba', 'abb', 'baa', 'mggfba', 'mffgh']

# trade time for space
# no extra space but, but O(n) to index
def sortCA1(arr, customAl):
    return sorted(arr, key=lambda x: [customAl.index(c) for c in x])

# trade space for time
# extra space O(n), but O(1) to index
def sortCA2(arr, customAl):
    dt = {c: i for i, c in enumerate(customAl)}
    return sorted(arr, key=lambda x: [dt[c] for c in x])

# output: ['bba', 'baa', 'abb', 'mffgh', 'mggfba']

Here is a version which not use sorted function, we can use a bucket based on custom alphabet order. split the arr by 1st char, if one bucket has multiple elements then split by 2nd char recursively...kind of radix sort: one thing to mention, the length is different, so we should add a bucket to record none index str.

def sortCA3(arr, customAl):
    dt = {c: i + 1 for i, c in enumerate(customAl)}  # keep 0 for none bucket

    def bucket_sort(arr, start):
        new_arr = []
        buckets = [[] for _ in range(len(customAl) + 1)]

        for s in arr:
            if start < len(s):
                buckets[dt[s[start]]].append(s)
            else:
                buckets[0].append(s)

        for bucket in buckets:
            if len(bucket) == 1:
                new_arr += bucket
            elif len(bucket) > 1:
                new_arr += bucket_sort(bucket, start+1)
        return new_arr

    return bucket_sort(arr, 0)

test and output

customAl = 'dshbanfmg'
arr = ['bba', 'bb', 'abb', 'baa', 'mggfba', 'mffgh']  # add `bb` for test
print(sortCA4(arr, customAl))

edited May 9, 2019 at 2:49

answered May 8, 2019 at 2:11

recnac

3,7746 gold badges27 silver badges48 bronze badges

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

3 Comments

Sailormoon Over a year ago

Hi @recnac, i want to find a solution that doesn't use sorted function.

recnac Over a year ago

Hi, @Sailormoon, I have added a new solution without sorted, use bucket

Sailormoon Over a year ago

bucket sort is perfect for this type @recnac

Collectives™ on Stack Overflow

sort array based on custom alphabet order python

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related