Re: sort algorithm

Juha Nieminen said:

Richard Heathfield wrote:
Um, what you call counting sort, I call bucket sort. I'm probably
abusing the term.

Bucket sort is a completely different sorting algorithm.

Having done a little belated research, I beg to differ slightly. When your
data forms a contiguous range and you can afford enough buckets to have
one bucket per possible value (as was the case for this problem), bucket
sort effectively degenerates into counting sort. So I was half-right. :-)

<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
.

Relevant Pages

  • Re: Finding the max number in a list
    ... Come to think of it, a bucket sort could do it too, ... unless the "uniform distribution" precondition he mentioned was to allow most ... the elements of each histogram bucket end up consecutive in the array ...
    (comp.lang.java.programmer)
  • Re: Sorting algorithm for FPGA availlable?
    ... go towards 16N memory cycles which may use the fastest rate of memory ... Actually that would be bucket sort. ... In a V4 you can probably even hold 64k entries ...
    (comp.arch.fpga)
  • Re: What is the most fast sorting algorithm?
    ... Bucket sort is Oin the worst case. ... Because of various special characters such as ... So our bucket sort's worst case may well have running time of O ...
    (comp.programming)
  • Re: What is the name of this sort method?
    ... The segment from index positions LEFT to RIGHT ... Sounds very similar to a bucket sort (but not quite what most people ... Bucket sort sorts data with a small-ish set of distinct possible keys ...
    (comp.programming)
  • Re: optimize log parsing
    ... > I wouldn't bother with this 'bucket' stuff at all. ... parse methods by multiplying each log size by a coefficient. ... N ln N to sort the files, only has to be done once. ... > biggest file that fits the current bucket is ln N using a binary search ...
    (comp.lang.perl.misc)