TransWikia.com

Why do we should not to use simple count instead of cumulative count in Counting Sort?

Computer Science Asked by Alihaydar Gubatov on October 21, 2021

I have this piece of code for counting sort and it is "counting" sort, because it actually counts occurrences. And it doesn’t use cumulative sum. I want to ask why it is bad to not to use cumulative sum in counting sort algorithm? (BTW it has O(n) runtime complexity)

def my_counting_sort(lst):
    counts = (max(lst)+1) * [0] # n
    output = []
    for item in lst: # n
        counts[item] += 1
    for index in range(len(counts)): # n
        item = counts[index]
        while item > 0:
            output.append(index)
            item -= 1
    return output

One Answer

It is related to the stability of output this algorithm:
Stable sort: For same number appearing more than once in the input array, ties are broken by the rule that whichever number appears first in the input array appears first in the output array.
•The property of stability is important only when satellite data are carried around with the element being sorted.
•Counting sort is often used as a subroutine in radix sort. Counting sort’s stability is crucial to radix sort’s correctness.
Having a cumulative sum helps it in making it a stable sort.

Answered by Puneet on October 21, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP