ArrayList sortieren

[njoerd]

Also ich habe folgendes Problem.
Ich habe in einer Arrayliste koordinaten Paare gespeicher, jetzt möchte ich diese im kreis anorden, dazu bestimme ich ganz einfach welches der 2 zu vergleichenden koordinaren links und welches rechts liegt.
Dazu habe ich den java.util.Comparator überlager(heißt das so?) so weit funktioniert das jetzt auch, aber leider ist jetzt nicht garantiert das das letze und das Erste element in meiner ArrayListe auch der Bedingung von links und rechts genügen. Hat wer eine Idee oder hinweis für einen Sortieralgorithmus der auch das letzte mit dem ersten Element überprüft und ggf. vertauscht?.

grüße aus dem sonnigen Wien und lg

 

[WieselAc]

Also ein vernünftiger Algorithmus vergleicht immer alles so, dass das Ergebniss stimmt.

Was benutzt du denn zum Sortieren? Was Selbstgeschriebenes? Oder eine Java eigene Methode?

Poste am besten auch mal deine compare-Methode oder noch besser ein kleines Beispiel.

 

[njoerd]

Also in meiner Liste habe ich die Punkte P_1 bis P_n
P_0 ist mein "zentrum", jetzt möchte ich diese dem winkel nach sortiert haben, winkel sind aber schlecht,(zu ungenau für meine zwecke) Eigentlich genügt mir die aussage ob P2, links oder rechts von der gerade p1,p0 liegt, wenn links dann passt das wenn rechts dann muss man p1 mit p2 tauschen. Das funktioniert auch nur ist wenn ich das mit

java.util.Collections.sort

mache dann ist nicht garantiert das das das auch mit dem ersten und dem letzten Element gemacht wird. ich brauche das aber.

Zum vergleichen hab ich den

java.util.Comparator

überlagert


ein kleine Grafik

Ich hoffe man versteht was ich will

 

[bygones]

Die ansaetze soweit ich sie seh hier sind schon richtig. eine collection am einfachsten ueber Collections.sort sortieren lassen (siehe FAQ beitrag). Den Comparator brauchst du dann wenn die Objekte a) kein eigene definierte Ordnung haben oder b) du eine andere als die natuerliche Ordnung haben willst

mache dann ist nicht garantiert das das das auch mit dem ersten und dem letzten Element gemacht wird.

das versteh ich nicht... es werden beim sortieren im grunde alle elemente vergleicht, also auch das erste und das letzte...

 

[Guest]

das erste und das letzte werden schon irgendwann verglichen, aber nicht das erste mit dem letzten und das ist mein problem. Der Sortieralgorithmus müsste im "kreis" sortieren, also wenn er am ende ist wieder am anfang anfangen bis die ordnung wie gewünscht ist

 

[bygones]

das erste und das letzte werden schon irgendwann verglichen, aber nicht das erste mit dem letzten und das ist mein problem. Der Sortieralgorithmus müsste im "kreis" sortieren, also wenn er am ende ist wieder am anfang anfangen bis die ordnung wie gewünscht ist

oeh... das momentan fehlende mittagsessen mag meine gedanken kraft trueben, aber sortierer suchen der reihe nach das kleinste elemente aus der liste...

d.h. wenn einmal die liste sortiert ist, muss er nicht wieder von vorne anfangen.... und es wird auch das erste mit dem letzten verglichen, ansonsten waere eine sortierung nicht moeglich !

 

[Guest]

versuche es noch einmal zu erklären und habe dazu ein neues bild gemalt

Ich hätte jetzt gerne die punkte 1-5 gerne so sortiert das diese im Uhrzeiersinn in meiner Arrayliste stehen. Im moment stehen sie willkürlich. Sortiere ich diese wie oben wäre auch folgende Reihenfolge richtig

1 2 3 4 5

Jedoch würde der knoten 1 und 5 auch verglichen werden stimmt die bedingung nicht mehr, da 1 zu 5 jetzt rechts liegt und nicht links, obwohl die sortierung ansonsten richtig ist. Die gesuchte Reihenfolge zu dem Bild wäre also

2 3 4 1 5

 

[bygones]

wir kommen der sache naeher.

dein erstes sortieren ist ueber die natuerliche ordnung, ich geh mal davon aus du hast Integer objekte in der liste und rufst einfach Collections.sort auf.
Die natuerliche Ordnung von integer ist der zahlenwert, daher 1 2 3 4 5

was du nun willst ist eine spezielle sortierung. D.h. du brauchst entweder einen Comparator oder deine Klasse implementiert das Comparable interface.

Mal ein bsp mit Comparator (sagen wir deine Punkte werden durch Point Instanzen repraesentiert)

public UhrzeigerSinn implements Comparator<Point> {
   public int compare(Point o1, Point o2) {
		// nun vergleichst du die beiden punkte so wie du willst... und gibst dann an ueber den return wert ob o1 kleiner ist als o2 oder andersrum
	}
}

nun kannst du dann deine Liste sortieren lassen

List<Point> myPointList = new ArrayList<Point>();
// liste fuellen
Collections.sort(myPointList, new UhrzeigerSinn());

nun ist die liste so sortiert, wie du es definiert hast, also dann auch 2 3 4 1 5

 

[Guest]

in meiner liste sind objecte von koordinaten paaren, das stimmt und soweit hab ich das ja schon gemacht, den comperator überlagert mit meiner Bedingung welche auch so sortiert wie sie soll, nur eben müsste die sortierungsbedingung auch zw. erstem und letzen listeneintrag stimmen und das muss eben mit

Collections.sort

nicht sein.

also die Knotennummern sollten im Uhrzeigersinn sortiert werden, sicher sind die Knotennummern in der Reihenfolge

1 2 3 4 5

auch auf eine art und weise im Uhriegersinn, aber zw. 5 und 1 sind sie eben nicht im Uhrzeigersinn orientiert (ich müsste bei dieser sortierung nicht nur einmal im kreis fahren, sondern mehrmals) und das ist mein problem

 

[WieselAc]

Hab mir da jetzt echt ein paar gedanken drüber gemacht, aber ich versteh es leider immer noch nicht wie du da sortieren willst.

Was ich jedoch weiß ist, das Collections.sort() klappt. Wenn nicht ist dein Sortierkriterium falsch oder du hast andere Erwachtungen.. Wie auch immer in dem Fall für ich dir raten schreib die ein eigenes Verfahren, da weißt du 100% was passiert.

 

[bygones]

du verstehst nicht was ich meine.

Collections.sort klappt und sortiert alles (!) nach einem definierten kriterium. Es beruecksichtigt ALLE elemente der liste egal an welcher reihenfolge sie stehen.

Also du hast Koordinaten. Die muessen ja als Klasse vorliegen - nutzt die Point oder deine eigene Klasse dafuer ?

die frage die du dir stellen musst ist, was ist die mathematische definition, dass punkte im uhrzeiger voneinander liegen.

D.h. P1 ist dann links von P2 wenn Bedingung X vorhanden ist. Und genau diese Bedinungen X implementierst du dann in der compareTo methode. Die vergleicht zwei punkte und du sagst ihr wie zu vergleichen ist.

zb

sortiere mir alle punkte nach der X Koordinate:

public UhrzeigerSinn implements Comparator<Point> {
   public int compare(Point o1, Point o2) {
      return o1.x - o2.x;
   }
}

also.... nochmal langsam

sort sortiert wie du es ihm sagst, er sortiert komplett und beachtet alles. Du musst ihm sagen wie er sortieren soll, d.h. du musst mathematisch definieren, wann ein punkt im Uhrzeigersinn eines anderen punkts liegt !