Mike Mike - 1 month ago 7
Java Question

Most efficient way to sort by multiple fields in Java

I'm working on a project where I have a table in memory, for example:

field1 field2 field3 field4 field5
somevalue somevalue somevalue somevalue somevalue
somevalue somevalue somevalue somevalue somevalue
.
.
.
.
v


What is the best way to write a function that would allow a user to specify some non-predetermined permutation of fields by which to sort? (ex./ sort by field2, then field1, then field5). The best method I thought of so far is a recursive function, but it gets ugly pretty quick, especially with creating and managing 'subgroups' of rows within each column. Can somebody point me in a more efficient direction before I commit to this convoluted approach?

By the way, my table is stored as a list of arrays.

Answer

The key thing to realize here is that your search algorithm always stays exactly the same. The only thing that changes is your actual comparison function.

I would recommend using a standard sort in the Arrays or Collections class, but writing your own custom Comparable class or Comparator, whose compare method will use the data the user supplies. This is actually kind of interesting - I've only ever written Comparable classes that use fixed data, but this is exactly a use case for them.

All you need to do is write the function

public int compare(Row row1, Row row2) {
    // iterate over the columns *in order of the user-supplied priority*
    // return appropriately
}

Here's documentation on the Comparable class.

And Comparator.

Which one you need depends on what you're implementing, I forget the details but should be straightforward.

The key #2 thing here is that you can instantiate your ColumnPrioritiesComparable class before the priorities are set. e.g.

class ColPriComp implements Comparable<ColPriComp> {
    private volatile int[] priorities; // possibly static, or obtained some other way,
    // so there's only one shared among all classes

    @Override
    public int compareTo(ColPriComp other) {
        // use "priorities" to do the comparison
    }

    public void setPriorities(int[] newPriorities) {
        this.priorities = newPriorities;
    }
}
Comments