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

TheBigPJ wrote:
Good Morning/Evening,

I'm young and foolish but love to create new ideas. The one I am
currently pondering...... (a simple unoptermised version of it):

public void wastefulSort()
{
//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];
}

}

Assumptions:
This is run on a turing machine.
The input values do not repeat.
Assume any B space unused, it is null (not 0).
-------------------------------------------------

Is this not the quickest way of sorting numerical data? aka takes n
(or O(n))?

Thanks,
Peter
You can handle repeats:
for (int i = 0; i < A.length; ++i) {
B[A[i]]++;
}

This is actually documented many places as a type of sort. It is definitely space wasteful, and depending on your range and distribution, can yield a very fast or very slow result. You're example, B could be 8 long, and you could shift the values of A to the range of 0-7 (subtract the minimum).

However, if A had {2,6,MAX_INT-10}; all of a sudden B has to be MAX_INT-13 in length, and to *find* the highest value in B, you'd have to iterate nearly two billion entries (assuming 32bit ints)

To make matters worse, what if you have A be {4, MAX_INT, MIN_INT}

Now, you're indexes into B aren't "int", they would have to be long, and your memory size would have to be at least 4 gigs of integers (around 16gigabytes)

so, if you know the of A is small, and it is very densely populated, then you can use this method for a speed increase.

For a general solution where you don't know those details before hand, O(n*logn) is as good as it gets.

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
.

Relevant Pages