PDA

View Full Version : Sort Behaviour

diraviam
05-19-2006, 08:34 AM
I am puzzled by the Sort behaviour in JMSL witn Double.NaN

double[] testPvalues = new double[] {100,20,30,Double.NaN,40,500,60,70,Double.NaN,90,1 0,0,10,60,Double.NaN};

Arrays.sort(testPvalues );

returns

Sorted
0.0
10.0
10.0
20.0
30.0
40.0
60.0
60.0
70.0
90.0
100.0
500.0
NaN
NaN
NaN

com.imsl.math.Sort.ascending(testPvalues)

returns

Sorted
0.0
10.0
10.0
20.0
30.0
40.0
60.0
60.0
70.0
90.0
100.0
NaN
500.0
NaN
NaN

ed
05-19-2006, 08:58 AM
Didn't you know NaN comes both before and after 500? ;)

Just kidding. Somebody here will have a look at the source and see what's up.

diraviam
05-19-2006, 03:01 PM
If this is a bug, how long will it take to get a fix.

ed
05-23-2006, 07:59 AM
We have confirmed there is an issue when multiple NaNs are present. I'm surprised to see kind of thing appear, and we're currently investigating.

brian
05-24-2006, 12:29 PM
Hello diraviam,

The following code uses a heap sort algorithm after filtering NaNs. It extends the code referenced below. It provides for both an ascending and descending 1d array sort. I hope this helps you in the short term.

HeapSorter (http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm)

import java.io.*;
import com.imsl.math.*;

public class TestSort {
public static void main(String args[]){
double[] tp = new double[] {100.0,20.0,30.0,Double.NaN,40.0,500.0,60.0,70.0,D ouble.NaN,90.0,1.0, 0.0,0.0,10.0,60.0,Double.NaN};
HeapSort ts = new HeapSort();
ts.ascending(tp);
PrintMatrix pm = new PrintMatrix();
pm.print(tp);
pm.print(ts.getOrder());
tp = new double[] {100.0,20.0,30.0,Double.NaN,40.0,500.0,60.0,70.0,D ouble.NaN,90.0,1.0, 0.0,0.0,10.0,60.0,Double.NaN};
ts.decending(tp);
pm.print(tp);
pm.print(ts.getOrder());
}
}

/* modified heapsort from code
* http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm*
*
* The following code uses a heap sort algorithm after filtering NaNs.
* It extends the code referenced above. It provides for both an ascending
* and descending 1d array sort.*/

public class HeapSort {
private double[] tp = {0.0};
private int[] index = {0};
private int end=0;

public double[] ascending(double[] input){
tp=input;
index = new int[input.length];
for (int i=0; i<tp.length; i++) index[i]=i;
end=tp.length-1;
filter();
heapsort();
return tp;
}

public double[] decending(double[] input){
double dtmp=0.0;
int itmp=0;
tp=ascending(input);
for (int i=0, j=tp.length-1; i<j; i++,j--){
dtmp=tp[i];
tp[i]=tp[j];
tp[j]=dtmp;
itmp=index[i];
index[i]=index[j];
index[j]=itmp;
}
return tp;
}

private void filter(){
for (int i=0;i<end;i++){
if (Double.isNaN(tp[i])){
while (i<end && Double.isNaN(tp[end])) end--;
tp[i]=tp[end];
index[i]=end;
tp[end]=Double.NaN;
index[end]=i;
end--;
}
}
end++;
}

private void heapsort(){
buildheap();
while (end>1)
{
end--;
exchange (0, end);
downheap (0);
}
}

private void buildheap()
{
for (int v=end/2-1; v>=0; v--)
downheap (v);
}

private void downheap(int v)
{
int w=2*v+1; // first descendant of v
while (w<end)
{
if (w+1<end) // is there a second descendant?
if (tp[w+1]>tp[w]) w++;
// w is the descendant of v with maximum label

if (tp[v]>=tp[w]) return; // v has heap property
// otherwise
exchange(v, w); // exchange labels of v and w
v=w; // continue
w=2*v+1;
}
}

private void exchange(int i, int j)
{
if(Double.isNaN(tp[j])) return;
double t=tp[i];
int t2=index[i];
tp[i]=tp[j];
index[i]=index[j];
tp[j]=t;
index[j]=t2;
}

public int[] getOrder(){
return index;
}
}

Regards,

brian

ed
06-26-2006, 12:14 PM
I just wanted to let everyone know that this behavior was fixed in the recent JMSL 4.0 and IMSL C# 4.0 release.