• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

How to sort with Java

Contents

  • Sorting without programming
  • Collections
  • Arrays
  • Interface Comparable
  • Comparator
    • External Comparator
    • Internal (anonymous) Comparator
  • More examples

Sorting is a very basic task that every programmer should be able to solve. In Python, you have sort and sorted. In C++, you can use operator overloading. I'll now tell you how to do basic sorting with Java. I will not write about natural language sorting or language-aware sorting. This is only about simple sorting with Java.

Sorting without programming

First of all, you have to make sure that you understand how sorting works - without Java, just in the real world.

What you need:

  • A container $C$ of objects
  • A way to compare two objects of the list at a time. The comparison, lets call it $\leq$ needs to satisfy the following conditions:
    • totality: $\forall x, y \in C: x \leq y \lor y \leq x$
    • antisymmetry: $\forall x,y \in C: x \leq y \land y \leq x \Rightarrow x = y$
    • transitivity: $\forall x,y,z \in C: x \leq y \land y \leq z \Rightarrow x \leq z$

Just think about what you sort in your everyday life:

  • Numbers
  • Words
  • Contries by population
  • Playing cards

You can apply different algorithms like selection sort which you would use for numbers or insertion sort which you would use for card games. No matter what algorithm you use, you need to be able to compare the elements.

Note that you can compare some objects, like countries, by many measures. You could look at the population, the birth rate or the area. No matter what you use to compare, the this will not influence the way you sort.

Collections

One way to sort is to implement the interface List. For all datastructures, that implement the interface List or one of its sub-interfaces you can use Collections an go on like this:

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> myList = new LinkedList<String>();
        myList.add("I");
        myList.add("think");
        myList.add("therefore");
        myList.add("I");
        myList.add("am");
        System.out.println(myList);
        Collections.sort(myList);
        System.out.println(myList);
    }
}

Output:

[I, think, therefore, I, am]
[I, I, am, therefore, think]

Note that I didn't write a Comparator or implement Comparable as String has one by default. Don't mix Collections and Collection! A Set is a Collection, but it is not sortable. Collections is a class that you can use for sorting. Like Math, that has utilities like sqrt

Arrays

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String[] myStrings = new String[5];
        myStrings[0] = "I";
        myStrings[1] = "think";
        myStrings[2] = "therefore";
        myStrings[3] = "I";
        myStrings[4] = "am";

        System.out.println(Arrays.asList(myStrings));
        Arrays.sort(myStrings);
        System.out.println(Arrays.asList(myStrings));
    }
}

Interface Comparable

This is an example how you could implement Comparable.

Country.java

public class Country implements Comparable<Country> {
    int population;
    double area;
    String name;

    public Country(int population, double area, String name) {
        this.population = population;
        this.area = area;
        this.name = name;
    }

    @Override
    public int compareTo(Country o) {
        // a negative integer, zero, or a positive integer as this
        // object is less than, equal to, or greater than the
        // specified object.
        return this.name.compareTo(o.name);
    }

    @Override
    public String toString() {
        return name + ": " + population;
    }
}

Main.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Country> europe = new ArrayList<Country>();
        europe.add(new Country(82000000,350000,"Germany"));
        europe.add(new Country(60000000,360000, "France"));
        europe.add(new Country(20000000,100000, "Norway"));
        europe.add(new Country(30000000,500000, "Sweden"));
        europe.add(new Country(50000000,123000, "Spain"));
        System.out.println(europe);
        Collections.sort(europe);
        System.out.println(europe);
    }
}

Output:

[Germany: 81903000, France: 64667000, Norway: 4985900, Sweden: 9514406, Spain: 47212990, Switzerland: 8014000, Monaco: 36371]
[France: 64667000, Germany: 81903000, Monaco: 36371, Norway: 4985900, Spain: 47212990, Sweden: 9514406, Switzerland: 8014000]

You should definitely add JavaDoc and comment what you've compared. Note that it would sort the list in reverse order if you switched this.population - o.population; to o.population - this.population;. This would be bad style, as the JavaDoc of Comparable define the order. If you would like to sort in reverse, you should use Collections.reverse(europe);.

You can also use compareTo() within compareTo():

    @Override
    public int compareTo(Country o) {
        return this.name.compareTo(o.name);
    }

Comparator

If you need to compare objects in multiple ways, you might need to implement Comperator. If you only have to compare objects in one way, I would always use the Interface Comparable. It's easier to use.

External Comparator

An external Comparator PopulationDensityComperator.java could look like this:

import java.util.Comparator;

public class PopulationDensityComperator implements
        Comparator<Country> {

    @Override
    public int compare(Country o1, Country o2) {
        double o1Density = o1.population / o1.area;
        double o2Density = o2.population / o2.area;

        if (Math.abs(o1Density - o2Density) < 0.00001) {
            return 0;
        } else {
            return o1Density - o2Density;
        }
    }

}

and you would use it like this in the Main.java:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Country> europe = new ArrayList<Country>();
        europe.add(new Country(81903000,357121.41,"Germany"));
        europe.add(new Country(64667000,668763, "France"));
        europe.add(new Country( 4985900,385199, "Norway"));
        europe.add(new Country( 9514406,450295, "Sweden"));
        europe.add(new Country(47212990,504645, "Spain"));
        europe.add(new Country( 8014000, 41285, "Switzerland"));
        europe.add(new Country(   36371,     2.02, "Monaco"));
        System.out.println(europe);
        Collections.sort(europe);
        System.out.println(europe);
        Collections.sort(europe, new PopulationDensityComperator());
        System.out.println(europe);
    }
}

Your output would be:

[Germany: 81903000, France: 64667000, Norway: 4985900, Sweden: 9514406, Spain: 47212990, Switzerland: 8014000, Monaco: 36371]
[France: 64667000, Germany: 81903000, Monaco: 36371, Norway: 4985900, Spain: 47212990, Sweden: 9514406, Switzerland: 8014000]
[Norway: 4985900, Sweden: 9514406, Spain: 47212990, France: 64667000, Switzerland: 8014000, Germany: 81903000, Monaco: 36371]

Internal (anonymous) Comparator

You can also directly implement the comperator where you need it:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Country> europe = new ArrayList<Country>();
        europe.add(new Country(81903000,357121.41,"Germany"));
        europe.add(new Country(64667000,668763, "France"));
        europe.add(new Country( 4985900,385199, "Norway"));
        europe.add(new Country( 9514406,450295, "Sweden"));
        europe.add(new Country(47212990,504645, "Spain"));
        europe.add(new Country( 8014000, 41285, "Switzerland"));
        europe.add(new Country(   36371,     2.02, "Monaco"));
        System.out.println(europe);
        Collections.sort(europe);
        System.out.println(europe);
        Collections.sort(europe, new Comparator<Country>(){
            @Override
            public int compare(Country o1, Country o2) {
                double o1Density = o1.population / o1.area;
                double o2Density = o2.population / o2.area;

                if (Math.abs(o1Density - o2Density) < 0.00001) {
                    return 0;
                } else if (o1Density > o2Density) {
                    return 1;
                } else {
                    return -1;
                }
            }
        });
        System.out.println(europe);
    }
}

Your output would be:

[Germany: 81903000, France: 64667000, Norway: 4985900, Sweden: 9514406, Spain: 47212990, Switzerland: 8014000, Monaco: 36371]
[France: 64667000, Germany: 81903000, Monaco: 36371, Norway: 4985900, Spain: 47212990, Sweden: 9514406, Switzerland: 8014000]
[Norway: 4985900, Sweden: 9514406, Spain: 47212990, France: 64667000, Switzerland: 8014000, Germany: 81903000, Monaco: 36371]

I don't recommend this way for some reasons:

  • It is more likely that your code gets more difficult to read
  • It's more difficult to reuse your code (you can't use the same Comparator in another location)
  • It's more difficult to extend your code

An argument for such an Comparator might be, that it is easier to read. But this is only an argument if the Comparator is very short.

More examples

  • StackOverflow: java class implements comparable

Published

Jan 8, 2013
by Martin Thoma

Category

Code

Tags

  • Java 36
  • Programming 52
  • sorting 3

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor