美文网首页
Variable Letter Count Sort.

Variable Letter Count Sort.

作者: R0b1n_L33 | 来源:发表于2018-03-19 19:23 被阅读6次

Θ(n) where n is the total letter count

def niblleLetterFromWords(words:[])->[]:
    # diff = 'a' - 1; 
    # As words starting with 'a' is stored underneath 
    # index 1 and so forth similarly.
    # Index 0 serve as a residency of NULL -- b''
    # So the scope of buckets is 27 which consists of
    # 1 bucket for b'' and the rest buckets for 
    # corresponding 26 alphabet letters.
    diff = 96
    scope = 27
    buckets = [[] for _ in range(scope)]
    for word in words:
        if not word:
            buckets[0].append(b'')
        else:
            buckets[word[0]-diff].append(word[1:])

    outcomes = buckets[0]
    # Do not deal with b'' set otherwise causing infinite loop
    for i in range(1,scope):
        bucket = buckets[i]
        lenOfBucket = len(bucket)
        if lenOfBucket > 0:
            sortedBucket = niblleLetterFromWords(bucket)
            prefix = (i+diff).to_bytes(1,byteorder='big')
            for i in range(lenOfBucket):
                sortedBucket[i] = prefix + sortedBucket[i]
            outcomes += sortedBucket
    return outcomes

def variableLetterCountSort()->[]:
    scope = 5
    amount = 100
    src = []
    # Build bytes via ASCII range of alphabet.
    alphabet = bytes(range(97, 123))
    for i in range(amount):
        src.append(bytes(choices(alphabet,k=randrange(scope))))
    return niblleLetterFromWords(src)

相关文章

网友评论

      本文标题:Variable Letter Count Sort.

      本文链接:https://www.haomeiwen.com/subject/wkapqftx.html