Most efficient way to sort by multiple fields in Java

Question

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 1

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;
    }
}

Most efficient way to sort by multiple fields in Java

Sign up