lexikografisch sortieren

[alex]

hallo!

ich möchte zwei strings lexikographisch sortieren,
verstehe aber nicht so ganz wie das geht.
ich dachte es geht irgendwie mit compareTo();.

hoffe dass mir das jemand vielleicht mit einem beispiel erklären kann so dass ich was damit anfangen kann.

mfg. alex

[Slyh]

Hallo,

ich möchte zwei strings lexikographisch sortieren,
verstehe aber nicht so ganz wie das geht.
ich dachte es geht irgendwie mit compareTo();.

Ja, diese Methode kann man u.a. dazu verwenden. Die Methode compareTo(Object)
wird im Interface "Comparable" deklariert. Die Klasse String implementiert
wiederum "Comparable", so daß du String auf bestimmte Weise (nämlich
lexikographisch) zumindest miteinander vergleichen kannst.
Die Entscheidung, ob nun String1 oder String2 "größer" oder "kleiner"
ist, nimmt dir also die fertige compareTo()-Implementierung in der
Klasse String ab.

Du kannst Strings jetzt verschiedenartig sortieren. Du könntest z.B.
eine java.util.Collection haben, beispielsweise eine ArrayList.
Um diese zu sortieren, bietet die Klasse java.util.Collections die
Methode sort(List) bzw. sort(List, Comparator).
Bei der ersten Variante wird die Liste in ihrer natürlichen Reihen-
folge sortiert. D.h., daß die Elemente so sortiert werden, wie sie
das gerne hätten. Hierzu wird nichts anderes getan als e1.compareTo(e2)
aufgerufen. Damit das geht, müssen alle diese Elemente natürlich
Comparable implementieren. Ist dies nicht der Fall, wird eine
Exception geworfen. (Siehe JavaDoc zu sort(List).)

Möchtest du also Strings lexikographisch sortieren, dann reicht
also schon der folgende Aufruf:
  Collections.sort(myStringList);

Vorausgesetzt deine Strings befinden sich in einer Liste (Interface
java.util.List).

Möchtest du die Elemente nicht entsprechend ihrer natürlichen Reihen-
folge absteigend sortieren, mußt du einen eigenen Comparator angeben,
der dann die Objekte jeweils vergleicht. Das Interface Comparator
findest du auch im Package java.util.

Möchtest du die Liste bspw. aufsteigend (d.h. "Z" zuerst) sortieren,
dann würde deine Comparator bspw. so aussehen:

class MyStringComarator implements Comparator
{
    public int compare(Object e1, Object e2)
    {
        return -1 * ((Comparable)e1).compareTo(e2);
    }
}

Hier würde jetzt also wieder compareTo des Elements verwendet werden,
die Reihenfolge durch das umgekehrte Vorzeichen aber vertauscht werden.
Wieder müßte das Element das Interface Comparable implementieren, da
sonst eine ClassCastException auftreten würde.

Angenommen deine Strings befinden sich nicht in einer Liste, sondern
in einem Array, dann hilft dir die Klasse java.util.Arrays weiter.
Diese hat verschiedene sort()-Methoden, u.a. sort(Object[]), die
wieder in der natürlichen Reihenfolge sortiert.

Gruß
Slyh

[Philipp Hasenfratz]

Halihallo Slyh

public int compare(Object e1, Object e2)
    {
        return -1 * ((Comparable)e1).compareTo(e2);
    }

Nur aus Interesse kurz eine Frage:
Warum nicht einfach "return ((Comparable)e2).compareTo(e1);"?
Ist nach Comparable dieselbe Aussage, denn
----------
The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo
(x)) for all x and y.
----------

aber...
a) es ist performanter
b) es ist ggf. besser lesbar, obwohl die Lesbarkeit genau auch ein
   Faktum für "-1 * ..."  sein kann (ich könnte mir vorstellen, dass
   dies genau Dein Beweggrund war, es so zu schreiben).

Ansonsten (auch) von meiner Seite aus Danke für die schönen
Ausführungen. Immer wieder interessant von Dir zu lesen.

Viele Grüsse

Philipp

[Slyh]

Hallo Philipp,

public int compare(Object e1, Object e2)
    {
        return -1 * ((Comparable)e1).compareTo(e2);
    }

Nur aus Interesse kurz eine Frage:
Warum nicht einfach "return ((Comparable)e2).compareTo(e1);"?

Weil ich soweit gar nicht gedacht habe. :-)

Ist nach Comparable dieselbe Aussage, denn

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo
(x)) for all x and y.

Völlig richtig.

aber...
a) es ist performanter

Wird wohl so sein. Dürfte in diesem konkreten Fall aber sogar
unerheblich sein, da der Vergleich von Strings erheblich langsamer
ist, als eine Multiplikation mit -1.
(Trotzdem hast du recht.)

b) es ist ggf. besser lesbar, obwohl die Lesbarkeit genau auch ein
   Faktum für "-1 * ..."  sein kann (ich könnte mir vorstellen, dass
   dies genau Dein Beweggrund war, es so zu schreiben).

Ich halte beide Versionen für gleich schlecht lesbar. :)

Letztendlich wollte ich wirklich zeigen, daß sich durch ein Umdrehen
des Vorzeichens die Sortierreihenfolge ändern läßt. Daran, daß sich
dies auch durch eine einfache Vertauschung von e1 und e2 erreichen
ließe, habe ich -- wie schon geschrieben -- in dem Moment nicht
gedacht, sonst hätte ich es zumindest noch erwähnt.

Auf jeden Fall sollte man genau dokumentieren, was in der Methode
passiert, da sowohl die Version mit "-1", als auch die Version mit
vertauschtem e1 und e2 meiner Ansicht nach erst auf den 2. Blick
verständlich wird. (Und das bei einem Einzeiler...)

Ansonsten (auch) von meiner Seite aus Danke für die schönen
Ausführungen. Immer wieder interessant von Dir zu lesen.

Danke! Das freut mich zu lesen. :-)

Gruß
Slyh