Sortieralgorithmus

[Yanko]

Hallo zusammen,

Ich bin auf der suche nach einen Sortieralgorithmus, um meine Bilder, die sich in einer Liste befinden, in der richtigen Reihenfolge darzustellen.

Und zwar verfügt jedes Bild über die Eigenschaften: Layer, X und Y. Als 1. möchte ich alle Bilder nach Layern sortieren, der kleinste zuerst. Danach noch von unten nach Oben also der Kleinste y-Wert zuerst, die Layersortierung sollte aber erhalten bleiben und zum Schluss noch von links nach rechts, also beginnend mit dem kleinsten X Wert.

Das implementieren bereitet mir eher kein Problem, ich weiß nicht welcher Algorithmus am alltagstauglichsten für mein Problem ist. Ich hoffe ihr habt da etwas Erfahrung, den aus den Wikipediaartikeln und einzelnen Blogeinträgen bin ich nicht viel schlauer geworden.

mfg

Yanko

 

[SlaterB]

hier zeigt sich die Informatik von ihrer schönen Seite, der Sortieralgorithmus ist von deinen Daten und Sortier-Kriterien komplett unabhängig,
du kannst Collections.sort() nehmen oder einen beliebigen anderen aus der Stadard-Liste von Wiki & Co.

alle Sortieralgorithmen (in gewissen Grenzen, im Standard-Bereich, mag ganz exotische geben) haben gemein,
dass sie allein auf den Vergleich zweier Elemente aufbauen, ist Element A größer, kleiner oder gleich Element B?
wenn diese Information von einer Methode geliefert wird, läuft der Rest nach Schema F ab,

diese Methode musst du implementieren, entweder compareTo() in einer Klasse oder in einem Comparator, siehe Standard-Lehrbücher
Galileo Computing :: Java ist auch eine Insel - 13 Einführung in Datenstrukturen und Algorithmen

eine einfache Methode, die sich erst Layer X von zwei Elementen (die als Parameter reinkommen) vergleicht,
dann gegebenenfalls Layer Y usw.,
paar simple ifs + Collections.sort() und alles läuft

 

[Dow Jones]

Da du ja nach einem Algorithmus gefragt hattest: Solange keinen besonderen Bedingungen vorliegen würde ich ganz pauschal zu Quicksort raten. Der ist schnell, einfach zu implementieren und kann von mehreren Sortierschlüsseln profitieren. Die Sortiermethoden von Java (und anderen Sprachen) verwenden - soweit ich mich erinnere - ebenfalls Quicksort. Damit macht man nichts verkehrt.

 

[Yanko]

Hallo,

Bei Wikipedia hab ich jetzt erfahren das der Quicksort instabil ist und da ich ja nach mehreren Kriterien sortiere, wäre da nicht der Mergesort besser? Das Prinzip ist ja bei beidem ähnlich.

mfg

Yanko

 

[SlaterB]

instabil hängt nicht von der Art der Suchkriterien ab,
wie gesagt gibt es eine Methode die zwei Elemente vergleicht, auf welche Weise ist ganz egal,
der Rest liegt dann im Algorithmus, Quicksort mag instabil sein, ja

Collections.sort() verwendet Mergesort, wie schon in der API leicht zu lesen ist

[..]
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance.
[..]

Collections (Java Platform SE 6)

 

[Dow Jones]

Bei Wikipedia hab ich jetzt erfahren das der Quicksort instabil ist und da ich ja nach mehreren Kriterien sortiere, wäre da nicht der Mergesort besser?

Ja, wenn du stabil sortieren möchtest dann kannst du freilich den Mergesort verwenden, klar. Solange du nicht gerade eine Millionen Bilder hast kannst du eigentlich ohnehin jeden beliebigen Algo einsetzen; so viel tut sich da nicht. Der Quicksort war halt eine pauschale Empfehlung.


PS@SlaterB: Und wieder etwas gelernt. Ich wusste wohl noch das bei C der Quicksort verwendet wird, bei Java habe ich ehrlich gesagt gar nicht nachgesehen. Das habe ich gerade nachgeholt, und in der Collections Api den Satz gefunden: ...the algorithm used by sort does not have to be a mergesort, but it does have to be stable. Du weisst nicht zufällig auch ob es dafür einen besonderen Grund gibt (abgesehen davon das es "schöner" ist als instabiles sortieren), oder?

 

[SlaterB]

ich kann nur vermuten dass das irgendwo für die Collections-Klasse/Spezifikation so steht,
eben ja durchaus auch in der Doc der Methode,
dann verlassen sich andere darauf, daher dieser Implementierungshinweis,

ich vermute ebenso dass es initial eine freie Entscheidung war und ja wohl die richtige,
sonst hätte Collections.sort() einen beachtlichen Makel, das ginge ja gar nicht bei diversen Sortier-Einsätzen

 

[California]

So wie ich das sehe, ist nicht der Sortieralgorithmus Dein Problem, sondern die grösser / kleiner Entscheidung.
Genau dafür gibt's den java.util.Comparator.
Schau dir mal dazu die Javadoc an und machs mit

Collections.sort( List, Comparator );

Es ist völlig Banane einen eigenen Sortieralgorithmus zu implementieren, den gibt's original in Java.

 

[Landei]

"instabil" bedeutet in diesem Zusammenhang nur, dass die Reihenfolge zweier als "gleich" angesehenen Objekte nicht festgelegt ist. Wenn ich also Personen nur nach Vornamen sortiere, ist nicht klar, ob Quicksort "Hans Meier" vor oder nach "Hans Müller" liefert. Sind alle Werte sowieso unterschiedlich, oder "gleiche" Werte wirklich ununterscheidbar, ist "instabil" völlig irrelevant (während dagegen ein Buch, das nicht von Elefanten handelt, irrelefant ist).