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.
Hackers beware! This problem is egregiously flawed: it fundamentally misunderstands counting sort; it is not just "go through the counts and print each one repeatedly"! The very first paragraph correctly states that often when we sort, the keys may be attached to satellite data. In that case, this "repeatedly print" method fails, since the satellite data is not stored in the count array (unless you do something funny like put a queue of the objects in each slot in the counter).
The actual counting sort, as discussed on page 195 of Intro to Algorithms CLRS third edition is significantly different from the one suggested in this problem, and not only addresses satellite data correctly, but specifically has the property that it is stable, e.g. in the event of tied keys, the original order is guaranteed to be preserved. The basic idea is to convert the array of counts to an array of cumulative sums, then iterate through the unsorted array in reverse and copy over to a second array using the cumulative sums as indices. Here's an implementation:
Counting Sort 2
You are viewing a single comment's thread. Return to all comments →
Hackers beware! This problem is egregiously flawed: it fundamentally misunderstands counting sort; it is not just "go through the counts and print each one repeatedly"! The very first paragraph correctly states that often when we sort, the keys may be attached to satellite data. In that case, this "repeatedly print" method fails, since the satellite data is not stored in the count array (unless you do something funny like put a queue of the objects in each slot in the counter).
The actual counting sort, as discussed on page 195 of Intro to Algorithms CLRS third edition is significantly different from the one suggested in this problem, and not only addresses satellite data correctly, but specifically has the property that it is stable, e.g. in the event of tied keys, the original order is guaranteed to be preserved. The basic idea is to convert the array of counts to an array of cumulative sums, then iterate through the unsorted array in reverse and copy over to a second array using the cumulative sums as indices. Here's an implementation: