Re: New technology, old idea.... why not?

TheBigPJ wrote:
[...sorting...]
//Using todays technology, of a lot of unused space
int[] A = {5,4,3,2,9};
int[] B = new int[1000];

for(int i = 0; i < A.length; i++)
{
B[A[i]] = A[i];
}
[..]
Is this not the quickest way of sorting numerical data? aka takes n
(or O(n))?

This is indeed pretty fast. There is a variation of the same:

B[A[i]] += 1;

i.e. you simply count the number of times the integer occurred, then you can
also use e.g. zeroes.

Drawbacks:
- the range must be known
- the number of elements in the range must be finite
- the range should be small
because this information is needed to dimension the counter array ('B' in
this case). Note: with a not-so small range or with unknown range you can
still use a tree instead of an array, but then the algorithm degrades
accordingly.

Assumptions:
This is run on a turing machine.

Why not on a computer? ;^)

Uli

--
Sator Laser GmbH
Geschäftsführer: Michael Wöhrmann, Amtsgericht Hamburg HR B62 932

.