wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Need Helping Sorting Array of Doubles But Need To Know Index Position Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Need Helping Sorting Array of Doubles But Need To Know Index Position" Watch "Need Helping Sorting Array of Doubles But Need To Know Index Position" New topic
Author

Need Helping Sorting Array of Doubles But Need To Know Index Position

Andrew Ceronoski
Greenhorn

Joined: Apr 21, 2009
Posts: 16
Hey,

I am having trouble sorting an array of doubles that I created, and still be able to keep the index of the array.

Here is my code: (Each array was declared earlier in the script as public)



After the sort is done, the zeroth item is the lowest double number. However, i need to know where it was initially in terms of its position (r) in the array, so I can resample my distribution and replace its value.

Any ideas on a better method or a solution would be great! Thank you in advance for the help.

fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11168
    
  16

Two possible things to try...

make two copies of the original array, and don't sort one. of course, if you need to say "where WAS the value 18.8263", you might have issues finding it if your array is large.

another thing would be to create a new class that stores a value and the original position. put those into your array, and sort appropriately. Then, when you pull out the element at position 0, you can get element.value and element.orig_pos


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
James Dixon
Ranch Hand

Joined: Jun 20, 2009
Posts: 32
Rather than creating a new class to do this you could also use a Map storing the double values as keys and their indexs as the associated values, that way you can retreive the original index just by passing the double value into the Map.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19655
    
  18

James Dixon wrote:Rather than creating a new class to do this you could also use a Map storing the double values as keys and their indexs as the associated values, that way you can retreive the original index just by passing the double value into the Map.

That was exactly what I was thinking of. A TreeMap would be just perfect for this.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
James Dixon
Ranch Hand

Joined: Jun 20, 2009
Posts: 32
On reflection, there is an issue.
How would you retreive the index of the double value if there was a duplicate (i.e. 1.0, 2.1, 1.0, 3.2, ...)?

Unfortunately, if this is likely to happen you will have to wrap the double in a new Class which can't be directly compared to the next value, otherwise you will find when you try to retrieve the index you won't know which one to go to. In fact, in a Map any previous key, value pair will be overwritten when putting in any subsequent double that is the same as a previous one.

I hope I haven't confused things too much...
Below is a very simple implementation, which may help explain things a bit better.
Note it is in no way perfect and I haven't used the TreeMap as suggested by Rob. This isn't because it can't be, but more that I've never used it before.

Any way hope this helps:

The above class is something quick and dirty which creates an array of MyDoubles adds them to a Map along with their index and finally sorts the array.

Below is the implementation of MyDouble. The only thing to note here is that I have implemented Comparable, if you don't then you can't use Arrays.sort(...) in Blah


Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19655
    
  18

James Dixon wrote:On reflection, there is an issue.
How would you retreive the index of the double value if there was a duplicate (i.e. 1.0, 2.1, 1.0, 3.2, ...)?

Ooh, I hadn't even thought of that. That does indeed pose problems.

TreeMap will not work without your MyDouble, because TreeMap uses compareTo instead of hashCode/equals.

If you need doubles, a sorted List or Set would be more logical. You'll need a new class for storing the double - position combination. I would then use a TreeSet:
This will sort on double value first. If however two double values are equal it will not regard them as equal but sort those on position.
Nev Mehta
Greenhorn

Joined: Jan 09, 2007
Posts: 26
I guess the reason TreeMap doesnt work is that it doesnt allow duplicate keys. Could you elaborate on this line a little further?
TreeMap will not work without your MyDouble, because TreeMap uses compareTo instead of hashCode/equals.


Thanks
Neville
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
I was thinking of an implementation like Rob's, only slightly more generic:





Then you can sort the List of Pairs by the fitst element. It takes a little bit more code, but the pieces can be reusable if that is desirable.

Edit: I forgot the forum software mangles nested angle braces.



Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19655
    
  18

Nev Mehta wrote:I guess the reason TreeMap doesnt work is that it doesnt allow duplicate keys. Could you elaborate on this line a little further?
TreeMap will not work without your MyDouble, because TreeMap uses compareTo instead of hashCode/equals.


Thanks
Neville

If, for two objects a and b that are mutually comparable, a.compareTo(b) == 0, then the TreeMap will regard them as equal. Similarly, if a.compareTo(b) < 0 then a will be placed before b, and if a.compareTo(b) > 0 then a will be placed after b.

This behaviour can be overridden by using a Comparator when creating the TreeMap, but then a.compareTo(b) will simply be replaced by comparator.compare(a, b).
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Need Helping Sorting Array of Doubles But Need To Know Index Position
 
Similar Threads
Sorting of string elements in alphabetical order
Reading Array values from a file
Descending order and associating Array Elements in sort method to another's elements
need help with Arrays.sort() and compareTo()
getting values from for loop