Subset sorting

As stated, I would have to say no.

My arugmet is this. Here is list A

1 2 3 4 5 6 7 8 9 ...

It is a sorted list of integers. B is a subset of that list (assuming elements of B are all distinct)

How does the fact that I know the sort order for the integers help me improve the sort time for a collection of integers? The sort order for the integers is something that I know in advance of every sort that I have ever done and it has never helped me before in reducing a sort from the generic nlogn

If I assume that all of B is not distinct, then my list A expands to be something like

11111222222233333334444444

where I repeat each element by the size of list B.

I am not saying that having list A can never help you improve the sorting of list B, for indeed, if you know some information about A you can use that to help you sort B.

For example, Hash the list B and keep a count on how many of each element was in B. Given that hashing is O(1) this is O(n). Then run the list A, hashing each element to see if it was in the table and and for each element that is in the hash table you now have the multiplicity of that element so you can build the list in one single pass through list A. Since list A is at least as long as list B the total runtime of this algorithm is O(M) where M is the size of list A. if M is on the order of N you can do your sort in better than NlogN.

So, A can help improve the sort time of B if there is some restriction on the nature of A, but without some qualification, I don't think it helps.

marlin314a at 2007-7-15 19:42:08 >

A and B are roughly of the same size with distinct values. Unfortunately, nothing else is known about A or B.

I was wondering if finding the median of B (or something similar) with insertion sort could help. I don't see how, but it could be a good way to approach the problem.

Another approach was to use an elevator algorithm (go in one direction in A till the end and start over again) - the performance would then depend on how sorted B originally was.

Learnablea at 2007-7-15 19:42:08 >

Thanks. The paper has some good formal information on sorting.

Though I initially posted the problem for integers, A and B both contain floating point numbers. So, signature sort is not applicable. I considered flashsort (which probably boils down to doing on interpolation search on A), but the numbers are not uniformly distributed.

Array A has 10000 elements and is fixed. B is sorted more than 2000 times during a run. During the first 200 or so iterations the size of B is around 0.7 times the size of A and during the rest of the iterations, the size of B is around 0.1 times the size of A. Currently I am using Collections.sort() but it is quite slow.

Learnablea at 2007-7-20 17:22:41 >

> but the overhead must be minimum in order

> for

> it to be faster then an algorithm like quick-sort.

Thats why I am hesitating using radix sort. The precision of the sort is important to every digit, and the numbers are double precision.

Here is a good article on flashsort:

http://www.neubert.net/Flapaper/9802n.htm

Learnablea at 2007-7-20 17:22:41 >

The Twos Complement Notation of floating point numbers has the property thata comparison uses the same operation in the CPU as for integer numbers. Therefore you could transform your floating point numbers into integer numbers that have the same bit representation, sort, and transform back. The additional transformation, of course, runs in O(n).

Methods to use would be Double.doubleToLongBits(double) and Double.longBitsToDouble(long)

horstmeyera at 2007-7-20 17:22:42 >

Still watching this topic, I see. Well if you are still interested I would suggest that you consider doing the following:

You say you have

U[k] an array of random values (I will assume double)

non-linear function f

Array A is f(([k]) sorted

Array B is subset of U[k] and you want to apply f to each element and sort.

create a class, Elt, to hold a single argument from U, the result of applying f to that element, a link to the next A Elt, and a marker int

class Elt{

double uk;;

double fofUk;

Elt next;

int marker = 0;

}

Create an array of Elts, one for each U[k], evaluate f on the U[k] element and srot that array by f of Uk. This is of course just your array A except that there is some extra stuff carried along with it.

Now thread the linked list. i.e. go throug the array of Elts and set

elt[k].next = elt[k+1]

set the last one to null.

Put elt[0] in a static location like Elt first; where you can always find it.

Now you can run the array A by following the next pointer. i.e. first is the first elt, first.next is the next elt, and so on.

Now you Hash the mess into a map. take each elt from the array and stuff into a Map the key will be the double uk, the data associated with it will be the Elt that has the value uk in it. So if you had 10000 elements in the array A you will have a HashMap that has 10000 Elts in it all indexed by their uk values.

So now you take a list B that is a subset of U[k]. Run the list B and for each U[k] that is on B look it up in the HashMap and find the Elt that has the same uk value. set the marker in that Elt to 1 (something different from the 0 that it was initialized with)

There is no need to calculate your non-linear function on the value from B because you already calcualted it once and stored it in the Elt. You just set the marker to 1 so that you know that this Elt was on list B.

When you have finished marking each element that was on B, now you go to first, the start of the A linked list, and run the list skipping every element that does not have the marker set to 1. Just read off the fofUk value. There you are - list B sorted by f.

For your second different list B, just set the marker to 2 this time - hash look up each element in B, set marker to 2, then start at first and copy the values from all Elts that have marker set to 2.

I haven't really suggested anything different from what I suggested back in my original reply, just spelled it out in more detail. Have you considered doing something like that? Did you try it? Is there some reason that you think that this method will not be superior to sorting the array and recalculating your non-linear f over and over?

marlin314a at 2007-7-20 17:22:42 >