0

I was reading: https://en.wikipedia.org/wiki/Counting_sort and https://www.geeksforgeeks.org/counting-sort/

There is one little detail which I don't get at all, why to complicate things where they can be so much easier? What's the problem of allocating an array of size k where the field of numbers is [1...k] and count how many times each number appeared and lastly walking down the array and printing according to the counter in each cell.

Evg
  • 25,259
  • 5
  • 41
  • 83
algo
  • 101
  • 6
  • @Yunnosch I have mentioned what is k in the post, that's how counting sort works. Its time complexity is O(n+k) – algo Oct 25 '21 at 06:11
  • 2
    Why is this tagged "c++"? Please remove. The code on wikipedia is just pseudo-code. It makes not much sense to discuss "implementation" of it. – Ralf Ulrich Oct 25 '21 at 06:12
  • @AlanBirtles "In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. " So how is this in-place sorting? they used additional arrays... – algo Oct 25 '21 at 06:22
  • My professor claimed counting sort saves the order of similar-size members (ie if 1 is before 1' then it remains so in the output) maybe this is related? But what's the problem of using no counter but linked list in each cell? it's same time complexity and does the job of saving order @AlanBirtles – algo Oct 25 '21 at 06:27
  • 1
    Just an FYI: The geeksforgeeks site isn't a very good source for learning programming or languages. Take the example on the page you linked to, which have the all-around despised [`bits/stdc++.h`](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) header file, or using other non-standard (and non-portable) extensions like [variable-length arrays](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). And it's also more "C with cout" than "proper" C++. – Some programmer dude Oct 25 '21 at 06:35
  • Geeksforgeeks offers resources of extremely poor quality. Don't use that website, it's just a garbage collection. – Evg Oct 25 '21 at 07:54

1 Answers1

0

What's the problem of allocating an array of size k where the field of numbers is [1...k] and count how many times each number appeared and lastly walking down the array and printing according to the counter in each cell.

From your phrase "how many times each number appeared", it sounds like you're picturing an array of positive integers, where you want to sort them in increasing order, and where you can use those integers directly as indices in your helper array?

But that's not what the Wikipedia article describes. The algorithm in the Wikipedia article is for an array whose elements can have whatever data-type we choose, provided there's a function key that maps from that data-type to the set of indices in the helper array, with the property that we want to stably sort elements according to the result of key (so, if key(x) < key(y) then we want to sort x before y, and if key(x) = key(y) then we want to keep x and y in the same order they originally had).

In particular, the counting-sort algorithm in the Wikipedia article is useful as a component of radix sort: first you sort by the last digit (using a key function that gives the last digit of a number), then by the second-to-last digit, and so on, until an array of numbers is sorted.

There is one little detail which I don't get at all, why to complicate things where they can be so much easier?

A pro tip: we all usually think that our own code is "easier" and that other people are "complicating things", because code is easier to write than to read, so the code that we understand best is the code that we've come up with ourselves.

As it happens, in this case the Wikipedia code really is more complicated, because it serves a much more general use-case than you were picturing; but in general, it's not a good idea to just assume that everyone will agree that your code is the easy version and that others' is unnecessarily complicated.

ruakh
  • 175,680
  • 26
  • 273
  • 307
  • My suggestion still holds for non-numbers... Plus, what's the problem of using no counter but linked list in each cell? it's same time complexity and does the job of saving order @AlanBirtles – algo Oct 25 '21 at 06:29
  • Re: "what's the problem of using no counter but linked list in each cell?": That would *not* end up being simpler than Wikipedia's version, unless you assume that linked lists are already provided as a library that you don't need to worry about the details of. Re: "it's same time complexity": It's the same *asymptotic* complexity, but I think the constants would be much higher, because you'd need to allocate a bunch of nodes . . . unless you preallocate all the nodes and keep track of which ones you've used, but then that's even more complicated! – ruakh Oct 25 '21 at 06:33