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

java-programmer, New technology, old idea.... why not? 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

java-programmer >> New technology, old idea.... why not? TheBigPJ wrote:
> Is this not the quickest way of sorting numerical data? aka takes n
> (or O(n))?

The problem: Retrieving the data is very slow

java-programmer >> New technology, old idea.... why not? On 28 Feb, 13:12, Florian Huebner <email***@***.com>
wrote:
> TheBigPJ wrote:
> > Is this not the quickest way of sorting numerical data? aka takes n
> > (or O(n))?
>
> The problem: Retrieving the data is very slow

Logically that makes sense yes.

But is that actually an attribute (if you like) of sorting data? aka
sorting is really 'Sorting and Retrieving'?

Peter

java-programmer >> New technology, old idea.... why not? And if you count retrieving as part of this, then searching the data
will take 1 move?

So the simple trade off, of displaying all the data takes a long time
is justified by only taking 1 move to search?

Or is this not the case?

Peter

java-programmer >> 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

java-programmer >> 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))?

First, the idea is not new at all: It's a primitive
version of what is known as an "address calculation sort."

Second, the time complexity is O(A.length + B.length).
Since B.length must be as least as great as the "span"
of the A values, it can turn out to be the dominant term
in the run time. Consider int[] A = { 1, 1000000000 },
for example. Observe that even a two-element A may
require a B that is much longer than Java's maximum
array size.

Third, you'll have a hard time generalizing it to
sort the array double[] A = { 1.2, 1.3, 1.4, -Math.PI }.

All in all, I'd suggest you not invest a whole lot of
effort in "optermizing" this code.

--
Eric Sosman
email***@***.com

java-programmer >> New technology, old idea.... why not? Young
- Thinking sorting was so simple to solve

Foolish
- Used only a small set of data within a small range (should have
remembered that)
- Should have thought outside the 'box' more

Learned
- Have another array then that time is added to the time complexity
- This is called 'address calculation sort'
- The right way to spell "optimized"

Question
- Are we there then on sorting data? At the end? Or just very close
to it?

Thank you all,
Peter

java-programmer >> 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/>

java-programmer >> 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()

This is a pigeon-hole sort. (I don't know why so many mathematics and
other scientific theories come down to pigeons. I makes me think that
Douglas Adams got things almost right. He just substituted mice for
pigeons by mistake.)

Anyway... pigeon-hole sort:

http://en.wikipedia.org/wiki/Pigeonhole_sort

The next step up is the bucket sort, which actually very useful. See if
you can spot the logic of the follow up.

java-programmer >> New technology, old idea.... why not? TheBigPJ wrote:
> [...]
> Question
> - Are we there then on sorting data? At the end? Or just very close
> to it?

A lot depends on how you formulate the problem. If you
sort using pairwise comparisons and you have no exploitable
prior knowledge of the existing arrangement, then it's not
hard to show that the problem is O(N log N). These are the
assumptions usually made for "general-purpose" sorting, and
one can see why: in Java, it means you can sort anything
that implements Comparable or for which you can build a
Comparator, so the sorting methods don't need information
about the nature of the objects being sorted.

But "special-purpose" sorting is another matter! For
example, if you know that the original sequence is in order
except for possibly one pair of adjacent items, the problem
shrinks down to O(N). Or if you have a way to determine the
order of items without comparing them -- that's what your
method does, more or less -- you may be able to get to an
O(N) sort.

There's even an O(1) sort, which I've always seen explained
in terms of pasta. You've got many pieces of uncooked spaghetti,
and you want to sort them by length. So you pick 'em all up in
a bundle, hold it vertically, and slam one end down on the
counter. Lo! The tallest strand now stands higher than all
the others, and the shortest strand stands lower, and so on
for all the in-betweens. They're "sorted" in just one step,
and with zero comparisons! (Of course, the task of picking
out the strands in sorted order still lies ahead ...)

Finally, big-Oh is not the end of the tale. If I offer
you several O(N logN) sorting methods, would you be expect them
all to take the same amount of time on the same inputs? If you
do, you don't understand big-Oh!

--
email***@***.com

java-programmer >> New technology, old idea.... why not? On Thu, 28 Feb 2008 04:15:22 -0800 (PST), TheBigPJ
<email***@***.com> wrote, quoted or indirectly quoted someone who
said :

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

see http://mindprod.com/jgloss/radixsort.html
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com