We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. The Full Counting Sort
  5. Discussions

The Full Counting Sort

  • anthonyabunassar
     + 1 comment

    Finally, after 3 hours! Don't use Python's sort(): I assume that our memory usage is so constrained that we can't sort an array of 1000 things. Don't create a big string in memory (i.e. don't use join()). So:

    def count_sort_internal(a: list) -> list[str]:
    '''
    According to the examples online, this is how the 
    midpoint is calculated. The function is allowed
    to be destructive. 100 is the (exclusive) limit
    to the key.
    '''
    buckets = [[] for _ in range(100)]
    midpoint = len(a) // 2
    for i in range(midpoint):
        a[i][1] = '-'
    for i, (k, s) in enumerate(a):
        buckets[int(k)].append('-' if i < midpoint else s)
    result = [s for bucket in buckets for s in bucket]
    return result

# pylint: disable=C0103,C0116
def countSort(a: list):
    result = count_sort_internal(a)
    for i, s in enumerate(result):
        if i > 0:
            print(' ', end='')
        print(s, end='')