DEV Community

loading...

Discussion on: Counting Linearly With Counting Sort

Collapse
palle profile image
Palle

There are also other Θ(n) (linear runtime in best, average and worst case) sorting algorithms. The most popular one may be radix sort.

You sort an array digit by digit by partitioning it into buckets, one bucket for each digit. This step is repeated from least significant to most significant digit, so for k-bit integers, the runtime of the algorithm is Θ(n*k)

As only the partially solved array and buckets for the next iteration need to be stored, the algorithm is more space efficient, requiring only Θ(n) additional space.

An example in base 10 would be:

Input array:
[637850, 18387, 329361, 968160, 183352, 296430, 56942, 990013, 663578, 792961]

The array is partitioned into ten buckets based on the 0th digit (from the right):
[637850, 968160, 296430],[329361, 792961],[183352, 56942],[990013],[],[],[],[18387],[663578],[]

The partitioned array is then flattened and the process is repeated with the 1st digit:
[],[990013],[],[296430],[56942],[637850, 183352],[968160, 329361, 792961],[663578],[18387],[]

2. digit:
[990013],[968160],[],[183352, 329361, 18387],[296430],[663578],[],[],[637850],[56942, 792961]

3. digit:
[990013],[],[792961],[183352, 663578],[],[],[296430, 56942],[637850],[968160, 18387],[329361]

4. digit:
[],[18387],[329361],[637850],[],[56942],[663578, 968160],[],[183352],[990013, 792961, 296430]

5. digit:
[18387, 56942],[183352],[296430],[329361],[],[],[637850, 663578],[792961],[],[968160, 990013]

The array is flattened and we're done:

[18387, 56942, 183352, 296430, 329361, 637850, 663578, 792961, 968160, 990013]

Like counting sort it is also stable, out of place and not based on comparisons. It can even be extended to sort floating point numbers and strings.


Edit:
It also sounds awesome

Collapse
vaidehijoshi profile image
Vaidehi Joshi Author

Hi Palle,

I actually just wrote this week's post on radix sort, funnily enough ☺️ You can read it here: medium.com/basecs/getting-to-the-r...

Vaidehi