Arrays und Listen sortieren

[Beni]

Arrays und Listen sortieren
Immer wieder kommt es vor, dass man Arrays oder Listen sortieren muss.
Für beiden Containerarten gibt es vorgefertigte Sortieralgorithmen, man muss sie nur noch aufrufen.

Arrays mit primitiven Datentypen
Arrays werden mit den sort-Methoden der Klasse java.util.Arrays sortiert.
byte-, short-, int-, long-, float-, double-- und char-Arrays können direkt der entsprechenden Methode übergeben werden.

int[] array = new int[]{ 4, 6, 2, 7, 5, 8, 9, 3, 1 };
System.out.println( java.util.Arrays.toString( array ));
        
// hier wird sortiert
java.util.Arrays.sort( array );
        
System.out.println( java.util.Arrays.toString( array ));

Wie nicht anders zu erwarten, ist die Ausgabe:
[4, 6, 2, 7, 5, 8, 9, 3, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9]


Objekt-Arrays und Listen
Für Arrays werden die sort-Methoden der Klasse java.util.Arrays benutzt.
Listen (wie ArrayList, LinkedList, Vector, und alle anderen Implementation von List) werden mit den sort-Methoden der Klasse java.util.Collections sortiert.

Bei Objekten fragt sich, nach welchen Kriterien sortiert werden soll. Bei einem String ist das ja noch einfach: alphabetisch. Aber wie steht es z.B. mit Color-Objekten? Soll nach Helligkeit sortiert werden, oder nach dem Rot-Anteil?
Und wie soll dem Sortieralgorithmus das mitgeteilt werden?

Comparable
Falls sich für ein Objekt eine "natürlich Ordnung" finden lässt (eine Ordnung auf die man ohne gross nachzudenken kommt, und die auch mehr Sinn als alle anderen möglichen Ordnungen macht), kann man das Interface java.lang.Comparable benutzen:
Die Klasse, deren Objekte später sortiert werden, implementiert Comparable. Der Algorithmus wird die Methode compareTo aufrufen, um herauszufinden, welches von zwei Objekten grösser ist.
Der sort-Methode muss ausser dem Array oder der Liste nichts weiter übergeben werden.

Beispiel: Lampen werden natürlicherweise nach ihrer Helligkeit (gemessen in Lumen) sortiert.

Die Lampen-Klasse, die Comparable implementiert, würde also folgendermassen aussehen:

public class Lampe implements Comparable<Lampe>{
    private int lumen;
    private String name;
        
    public Lampe( String name, int lumen ){
        this.name = name;
        this.lumen = lumen;
    }

    // Die Methode wird durch Comparable vorgeschrieben.
    // Wenn "this < argument" dann muss die Methode irgendetwas < 0 zurückgeben
    // Wenn "this = argument" dann muss die Methode 0 (irgendetwas = 0) zurückgeben
    // Wenn "this > argument" dann muss die Methode irgendetwas > 0 zurückgeben        
    public int compareTo( Lampe argument ) {
        if( lumen < argument.lumen )
            return -1;
        if( lumen > argument.lumen )
            return 1;
            
        return 0;
    }
        
    @Override
    public String toString() {
        return name + " (" + lumen + " Lumen)";
    }
}

Der Aufruf von sort erfolgt gleich wie im ersten Beispiel und dem int-Array:

Lampe[] array = new Lampe[]{
    new Lampe( "Halogenmetalldampflampe", 6600 ),
    new Lampe( "Gewöhnlich 60W", 730 ),
    new Lampe( "Leuchtstoffröhre", 3250 ),
    new Lampe( "Natriumdampflampe", 8000 ),
    new Lampe( "Halogenlampe 12V/50W", 1050 ),
    new Lampe( "Kompaktleuchtstoffröhre", 2900 ),
    new Lampe( "Gewöhnlich 100W", 1350 ),
    new Lampe( "HQL 125W", 5000 )
};

System.out.println( java.util.Arrays.toString( array ));
        
// hier wird sortiert
java.util.Arrays.sort( array );
        
System.out.println( java.util.Arrays.toString( array ));

Die Ausgabe lautet dann:
(Unsortiert) [Halogenmetalldampflampe (6600 Lumen), Gewöhnlich 60W (730 Lumen), Leuchtstoffröhre (3250 Lumen), Natriumdampflampe (8000 Lumen), Halogenlampe 12V/50W (1050 Lumen), Kompaktleuchtstoffröhre (2900 Lumen), Gewöhnlich 100W (1350 Lumen), HQL 125W (5000 Lumen)]

(Sortiert) [Gewöhnlich 60W (730 Lumen), Halogenlampe 12V/50W (1050 Lumen), Gewöhnlich 100W (1350 Lumen), Kompaktleuchtstoffröhre (2900 Lumen), Leuchtstoffröhre (3250 Lumen), HQL 125W (5000 Lumen), Halogenmetalldampflampe (6600 Lumen), Natriumdampflampe (8000 Lumen)]

Comparator
Sollte sich keine natürliche Ordnung finden lassen, oder kann man - aus welchen Gründen auch immer - Comparable nicht benutzen, bietet sich als Ersatz ein java.util.Comparator an.
Ein Comparator besitzt eine einzige Methode compare. Diese Methode vergleicht zwei Objekte, und teilt dem Aufrufer mit, welches der Objekte grösser ist.
Falls "erstes Objekt" < "zweites Objekt", dann gibt compare etwas < 0 zurück.
Falls "erstes Objekt" = "zweites Objekt", dann gibt compare 0 (etwas = 0) zurück.
Falls "erstes Objekt" > "zweites Objekt", dann gibt compare etwas > 0 zurück.

Mit einem Comparator kann man die seltsamsten Vergleiche anstellen, z.B. die "Quardatigkeit von Rechtecken".

Zuerst die Rechtecks-Klasse:

public class Rechteck{
    private int breite, höhe;
        
    public Rechteck( int breite, int höhe ){
        this.breite = breite;
        this.höhe = höhe;
    }
        
    @Override
    public String toString() {
        return "Rechteck [Breite="+breite+", Höhe="+höhe+"]";
    }
        
    public int getBreite() {
        return breite;
    }
        
    public int getHöhe() {
        return höhe;
    }
}

Dann der Comparator, der die Quadratigkeit misst:

public class QuadratheitComparator implements Comparator<Rechteck>{
    public int compare( Rechteck a, Rechteck b ) {
        // je quadratischer, desto grösser
        double quadratheitA = quadratheit( a );
        double quadratheitB = quadratheit( b );
            
        if( quadratheitA < quadratheitB )
            return -1;
        if( quadratheitA > quadratheitB )
            return 1;
            
        return 0;
    }
        
    private double quadratheit( Rechteck r ){
        double min = Math.min( r.getBreite(), r.getHöhe() );
        double max = Math.max( r.getBreite(), r.getHöhe() );
            
        return min / max;
    }
}

Und dann natürlich der Aufruf der Sortieralgorithmus:

public static void test(){
    List<Rechteck> rechtecke = new ArrayList<Rechteck>();
    rechtecke.add( new Rechteck( 5, 7 ));
    rechtecke.add( new Rechteck( 2, 7 ));
    rechtecke.add( new Rechteck( 6, 4 ));
    rechtecke.add( new Rechteck( 9, 1 ));
    rechtecke.add( new Rechteck( 9, 8 ));
    rechtecke.add( new Rechteck( 3, 3 ));
    rechtecke.add( new Rechteck( 2, 5 ));
        
    print( rechtecke );
        
    // hier wird sortiert
    Comparator<Rechteck> comparator = new QuadratheitComparator();
    java.util.Collections.sort( rechtecke, comparator );
        
    System.out.println();
    print( rechtecke );
}
    
private static void print( List<?> list ){
    int index = 1;
        
    for( Object item : list )
        System.out.println( index++ + ": " + item );
}

Die Ausgabe lautet:
1: Rechteck [Breite=5, Höhe=7]
2: Rechteck [Breite=2, Höhe=7]
3: Rechteck [Breite=6, Höhe=4]
4: Rechteck [Breite=9, Höhe=1]
5: Rechteck [Breite=9, Höhe=8]
6: Rechteck [Breite=3, Höhe=3]
7: Rechteck [Breite=2, Höhe=5]

1: Rechteck [Breite=9, Höhe=1]
2: Rechteck [Breite=2, Höhe=7]
3: Rechteck [Breite=2, Höhe=5]
4: Rechteck [Breite=6, Höhe=4]
5: Rechteck [Breite=5, Höhe=7]
6: Rechteck [Breite=9, Höhe=8]
7: Rechteck [Breite=3, Höhe=3]

Weitere hilfreiche Klassen

TreeSet
Benötigt man eine Liste, die immer sortiert ist, aber die auch oft wieder verändert wird (Elemente kommen hinzu oder werden gelöscht), eignet sich ein java.util.TreeSet
Das TreeSet hält seine Elemente durch einen Comparator (wenn keiner angegeben wird, nimmt das TreeSet an, dass die Elemente Comparable sind) geordnet. Allerdings erlaubt das TreeSet keine zwei Einträge die gleich sind!

String - Der Collator
String implementiert zwar Comparable, aber seine compareTo-Methode ist ziemlich primitiv. Zum Beispiel wird diese Methode sagen, dass "Z" kleiner als "a" ist.
Eine schönere Sortierung kann man mit Hilfe eines java.text.Collators erreichen. Ein Collator ist nichts anderes als ein Comparator für Strings, der alphabetisch sortiert. Man kann nicht direkt einen Collator erzeugen, sondern muss die statische Methode getInstance verwenden.