Re: sort algorithm

Richard Heathfield wrote:
I used bucket-sort. For this application, I heartily recommend it.

Wouldn't a simple counting sort have been much simpler to implement
(and probably faster)? Something like:

size_t counts[101] = { 0 };

for(size_t i = 0; i < 100000000; ++i)
++counts[array[i]];

size_t arrayInd = 0;
for(int cInd = 0; cInd <= 100; ++cInd)
for(size_t counter = 0; counter < counts[cInd]; ++counter)
array[arrayInd++] = cInd;

The speed of this depends heavily on the actual integral type used in
the array. For example in my computer (3.4GHz Pentium4) sorting an array
of ints like this takes about 400ms, but if it's an array of chars
instead, it takes only 170ms.
.

Relevant Pages

  • Re: C newbie in a jam
    ... Richard Heathfield skrev: ... void, not VOID ... The first is a pointer to an array of ROW x COL doubles. ... attempt to define an array of ROW x COL pointers to double - an attempt ...
    (comp.lang.c)
  • Re: gcc: pointer to array
    ... >> array's name is used in a value context, is the address of the first ... "value" means when applied to an array. ... pointer to the first element of that array. ... Richard Heathfield ...
    (comp.lang.c)
  • Re: Char array only the 4th letter
    ... Richard Heathfield wrote: ... omit the extra and don't explicitly specify ... > 'abcdefghij' uses character delimiters instead of a string delimiter. ... > so your array must be 11 bytes in size. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: looking for name for data structure
    ... Richard Heathfield writes: ... It's the elements that are fat, not the array, but still ... ...provided nobody confuses it with a File Allocation Table. ...
    (comp.programming)
  • Re: Merge Sort in C - array output is same as input after sort routine completes
    ... One doubt I have is that to calculate the mem address of array why it ... has to be casted to unsigned char * why cant char* instead? ... Richard Heathfield wrote: ... problem to request me to post my fixes. ...
    (comp.lang.c)