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