Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

How would one sort a list of objects that have more than one sortable element?

Suppose you have a simple object Car and car is a defined as such:

class Car {
    public String make;
    public String model;
    public int year;
    public String color;
    // ... No methods, just a structure / container
}

I designed a simple framework that would allow for multiple SortOptions to be provided to a Sorter that would then sort the list.

interface ISorter<T> {
    List<T> sort(List<T> items);
    void addSortOption(ISortOption<T> option);
    ISortOption<T>[] getSortOptions();
    void setSortOption(ISortOption<T> option);
}

interface ISortOption<T> {
    String getLabel();
    int compare(T t1, T t2);
}

Example use

class SimpleStringSorter extends MergeSorter<String> {
    {
        addSorter(new AlphaSorter());
    }

    private static final class AlphaSorter implements ISortOption<String> {
        // ... implementation of alpha compare and get label
    }
}

The issue with this solution is that it is not easily expandable. If car was to ever receive a new field, say, currentOwner. I would need to add the field, then track down the sorter class file, implement a new sort option class then recompile the application for redistribution.

Is there an easier more expandable/practical way to sort data like this?

share|improve this question
4  
Look up the Comparator pattern or Comparer pattern. You simply just want to abstract the less than, equal or greater than comparison while leaving the rest of the algorithm intact. –  Peter Smith Dec 6 '12 at 22:13
    
Peter - you should move this to be an answer :-) –  Martijn Verburg Dec 6 '12 at 22:48
add comment

2 Answers 2

up vote 7 down vote accepted

actually you can use a comparator which has a method compare(a,b) which you can implement

then you can pass it in for the compare step (this is supported in nearly all standard libraries of most languages)

for example in java you can call

Collections.sort(fooList, new Comparator<Car>(){
    public int compare(Car a,Car b){
        return a.getModel().compareTo(b.getModel());
        // or compare what you want return -1, 0 or 1 
        // for less than, equal and greater than resp.
    }
});

to sort your lists according to a custom comparator

(there is a new lambda syntax you can use for this in the works for java)

this means there will be only one sorting algorithm to maintain and a bunch of comparators which can remain in the same class as what it is comparing, (or near the place where the comparing is taking place)

edit: also for a "tiered" sort you can implement something like:

public static Comparator<T> createTieredComparator(final Comparator<? super T> comp1, final Comparator<? super T> comp2){
    return new Comparator<T>(){
        public int compare(T a,T b){
            int res = comp1.compare(a,b);
            if(res!=0)
                return res;
            else
                return comp2.compare(a,b);
        }
    };
}

this will prefer the comparison made by comp1 and only return the result of comp2 when they would be considered equal according to comp1

share|improve this answer
    
I looks to be the better solution: hard to do less than add the field on the considered class and express "somewhere" how to deal with all the fields used in the comparison. –  mgoeminne Dec 7 '12 at 14:42
add comment

Implement java.lang.Comparable and use collections like java.util.TreeSet that rely on "natural ordering." Implementing the compareTo() method in the Comparable interface is a lot like implementing an equals() method - that link contains an example of both. It is critical to implement equals() and hashcode() if you implement compareTo() and all three must be compatible with each other!

private int compareNullHelper(Object a, Object b) {
    // sorts nulls first
    if (a == null) {
        if (b != null) { return -1; }
    } else if (b == null) { return 1; }
    return a.compareTo(b);
}

/** Sorts by make, model, year, color. */
@Override
public int compareTo(Car that) {
    // ensures consistency with equals()
    if (this.equals(that)) { return 0; }

    int ret = compareNullHelper(this.make, that.make);
    if (ret != 0) { return ret; }

    ret = compareNullHelper(this.model, that.model);
    if (ret != 0) { return ret; }

    ret = this.year - that.year;
    if (ret != 0) { return ret; }

    ret = compareNullHelper(this.color, that.color);
    if (ret != 0) { return ret; }

    // If you can't tell, return -1 which means that they are in the right
    // order but unequal - ensures consistency with equals()
    return -1;
}

Now you can write:

Set<Car> orderedCars = new TreeSet<Car>();
orderedCars.addAll(myCars);

If you need to sort according to different criteria, make additional Comparator classes (that's another Java API interface) for each sort order. If you make Car implement Comparable and the compareTo() method of your Car class goes by make, model, year, color, you might want to make a ByColorComparator implements Comparator that compares by color, year, make, model. Then say:

Set<Car> carsByColor = new TreeSet<Car>(new ByColorComparator());
orderedCars.addAll(myCars);

The built-in sorting in Java collections is insanely fast. For years Java collections have been one of the best things about the platform.

One thing to note is that this technique will work with Hibernate or JPA (if you have an open database session) to automatically grab related objects from the database that may be needed for sorting.

share|improve this answer
2  
I prefer the comparator variant: a car has no natural order and you should provide a comparator as one of the sorting strategies. Also, why play with Treeset if you only want to sort your collection? –  mgoeminne Dec 7 '12 at 14:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.