How to sort a two-dimension ArrayList

Go To StackoverFlow.com

5

I have a two-dimension ArrayList that contains double values:

ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 

In analogy with classic arrays , I would like to sort the "cols" of this matrix :I want to take the items having the same index in the sub ArrayLists, and then sort them. Like calling Collections.sort() for every column... By rows I mean the outer level and inner level are columns.

What is the proper way to do this? I thought about iterating over the matrix to invert it and then sort each row with Collections.sort() ? but maybe it's not the best solution because the matrix is about 400*7000 .

I can't use classic arrays since the size of the matrix is unknown.

Thanks for help.

2012-04-05 20:22
by Believer
I assume outer level represents rows, but it would be nice if you could state it in your question - ahanin 2012-04-05 20:30
are the doubles any specific numbers or just random? What do they signify - noMAD 2012-04-05 20:35
Have you looked at specialized matrix libraries such as JaMa? If one of them covers your requirements, it might save you a lot of time - Barend 2012-04-05 20:36
Also, do you just want then sorted by columns? Or should it be something like the smallest element in the matrix should be at 0,0 and the largest at N,M - noMAD 2012-04-05 20:37
@BarendGarvelink: I don't see any function implemented for sorting in the link you provided? It was a nice lib though, thanks! : - noMAD 2012-04-05 20:39
The doubles are calculated, they can be any double value. Concerning the columns I just want them sorted, no particular requirements - Believer 2012-04-05 20:53
@BarendGarvelink: Thanks for the link it looks interesting, but I see no sort in the library features, maybe it can be useful for inversion - Believer 2012-04-05 21:03


3

Do something like this:

    final int COLUMN = 5;
    Comparator<ArrayList<Double>> myComparator = new Comparator<ArrayList<Double>>() {
        @Override
        public int compare(ArrayList<Double> o1, ArrayList<Double> o2) {
            return o1.get(COLUMN).compareTo(o2.get(COLUMN));
        }
    };
    Collections.sort(list, myComparator);

Set COLUMN to whatever column you're sorting on.

Update:

Yes, this won't work at all.

I like ahanin's second suggestion to make your own List which wraps your original List. You would have to wrap the object returned by get() as well so that the variable wrappedList contains the column values and wrappedList.get(0) also returns a column of values. Then the sorting can work. I wonder what the minimum methods are that you have to implement for Collections.sort() to work on your List.

It would probably be easiest to just take someone else's quicksort and make it work with your list.

Here is one implementation: http://www.vogella.de/articles/JavaAlgorithmsQuicksort/article.html

2012-04-05 20:43
by Sarel Botha
The OP isn't asking to sort on a particular column, they're asking to sort the columns independently - trutheality 2012-04-05 21:20
My understanding is he wants to have all columns sorted, so we will actually have to move the Double elements between the Lists - Helmuth M. 2012-04-05 21:20
@SarelBotha: Yes I would like to sort each column independently, Collections.sort() should be called as many times as the number of columns (= The size of the inner ArrayLists) - Believer 2012-04-05 21:38
Thank you all for your responses, I will meditate on this tonight and tomorrow I will test the wrapper solution, if it doesn't work like I want I will implement a basic solution as proposed by trutheality, even if the loops are a little bit scary ^^ - Believer 2012-04-05 22:50


3

So here's an option that is like the inversion idea but instead of inverting the entire thing you are building one column at a time, sorting it, and discarding it.

ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 

for(int c=0; c<data.get(0).size(); c++) {
    List<Double> col = new ArrayList<Double>();
    for( int r=0; r<data.size(); r++ )
        col.add( data.get(r).get(c) );

    Collections.sort(col);

    for( int r=0; r<col.size(); r++ )
        data.get(r).set( c, col.get(r) );
}

I doubt that you will be able to get anything more efficient, besides perhaps the option of creating your own class that provides a view of a column of the table as a list.

2012-04-05 21:11
by trutheality


2

I got two crazy ideas: either to implement your own sorting algorithm that would be aware of your inverted matrix structure, or write an implementation of Collection that would wrap your structure and represent the column, which could later be used as an argument to Collections.sort(). With ArrayList this should be rather fast.

2012-04-05 20:29
by ahanin


2

Here is an approach to this situation of converting the data into an object array. Change column to whatever you like.

final int column = 3;
ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 

// Convert data into an object array
Object [] temp = data.toArray();

Arrays.sort(temp, new Comparator<Object>() {
    @Override
    public int compare(Object o1, Object o2) {
        // Get inner arrays to be compared by type-casting
        ArrayList<Double> temp1 = (ArrayList<Double>) o1;
        ArrayList<Double> temp2 = (ArrayList<Double>) o2;

        // Then compare those inner arrays' indexes
        return temp1.get(column).compareTo(temp2.get(column));
    }
});

// Clear the old one and add the ordered list into
data.clear();

for(Object o: temp)
{
    data.add((ArrayList<Double>) o);
}
2012-10-12 17:33
by Emin Buğra Saral


0

I guess if storage is not a problem you can use a SortedMap in your ArrayList. In that way you don't have to worry for sorting the elements.

ArrayList<SortedMap<Double,byte>> data;
2012-04-05 20:42
by Nitin Chhajer
How will this work? It would sort it by rows and that's not what he wants - noMAD 2012-04-05 20:45
I don't think that there is clarity between what are rows and columns. Moreover it is just a logical display which can be seen only when you traverse it. It all depends on the traversing technique used - Nitin Chhajer 2012-04-05 21:05


0

Not sure if i understood your Q correctly, but this will sort all "columns" (assuming outer level are rows and inner level are columns):

    final ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 
    //...

    final Integer[] rows = new Integer[data.size()];
    for(int i=0;i<rows.length;i++)
        rows[i]=i;

    int cols = data.get(0).size();
    for(int c=0;c<cols;c++)
    {
        final int colidx = c;
        Arrays.sort(rows,new Comparator<Integer>(){
            @Override
            public int compare(Integer arg0,
                    Integer arg1) {
                return data.get(arg0).get(colidx).compareTo(data.get(arg1).get(colidx));        
            }});    

        for(int i=0;i<rows.length;i++)
            data.get(i).add(colidx+1,data.get(rows[i]).get(colidx));
        for(int i=0;i<rows.length;i++)
            data.get(i).remove(colidx);
    }
2012-04-05 20:59
by Helmuth M.


0

You will have to visit all the elements in order to sort them in any case. So what you could do is this.

int temp[] = new temp[col.length];
int x = 0;
while(x < row.length)
{
    for(int i = 0; i<col.length; i++)
    {
        temp[i] = mat[x][i];
    }
    sort(temp);
    for(int i = 0; i<col.length; i++)
    {
        mat[x][i] = temp[i];
    }
x++;
}

The running time here would be O(n^2logn) but since you are sorting just 400 doubles that would not take much time. and since you have to visit each element in the matrix atleast once, you can't go below O(n^2)

2012-04-05 21:45
by noMAD
Ads