Collection Sort

[SideWinder]

Hi.
ich hab folgendes Problem:
Ich soll eine ArrayList<Point> sortieren, mit einem Divide & Conquer verfahren. Ergo dacht ich mir, nimmste Mergesort, da meines Wissens nach das Collectionsortverfahren, das man ja importieren kann, Mergesort ist.

Nun Meine Frage, ich will dass die Objekte entsprechend ihren X Koordinaten Sortiert werden, wie mache ich das?

Danke vielmals!!!!

 

[Wildcard]

Übergib einen Comparator

 

[Guest]

huh?

Ich hab doch folgendes, gell? :

Collections.sort(names);

und importiere dafuer:

import java.util.Collections;

Wo kommt denn da noch ein KComparator rein?
(ich hab das hier gefunden:
http://www.kiesler.at/article38.html?&MMN_position=55:42:54)

Kannst du mir ein kurzes Beispiel geben, bitte?

dangee

 

[tfa]

Du könntest dich mit kwonilchang zusammentun. Der hat das gleiche Problem (will allerdings Quicksort einsetzen).

 

[Beni]

Collections hat zwei sort-Methoden. Eine mit, eine ohne Comparator.
Unsere FAQ
zweite sort Methode

 

[tincup]

Worum es geht ist, dass du nur dann sortieren kannst, wenn du auch eine Ordnung auf deinen zu sortierenden Objekten definierst. Also musst du dem Sortierer beibringen, dass PunktA < PunktB genau dann wenn gilt PunktA.X < PunktB.X (genauer <= aber egal für hier).

Das machst du, in dem du entweder "Comparable" in deiner Point-Klasse implementierst (falls du auf den Code zugreifen kannst) oder eben einen Comparator erstellst. Beides würde zu einer Funktion führen, die du so implementieren musst, dass entweder -1, 0 oder 1 zurückgegeben wird. Je nachdem welcher der beiden Punkte (nach deiner Ordnungsdefinition) kleiner oder größer oder gleich dem anderen ist.

HTH

 

[kwonilchang]

Wie tfa schon geschrieben hat, habe ich das gleiche Problem, die ArrayList zu sortieren.

Habe in meine Point-Klasse jetzt mal Comparable implementiert:

class Point implements Comparable <Point>{
	int x;
	int y;
	
	Point (int x, int y){
		this.x = x;
		this.y = y;
	}
	
	public String toString (){
		String s = "";
		
		s = "" + "(" + x + ", " + y + ")";
		
		return s;
	}
	
	public int compareTo (Point p){
		if( this.x < p.x ) 
            return -1; 
        if( this.x > p.x ) 
            return 1; 
            
        return 0; 
	}
}

Weiß jetzt aber nicht, wie die Sortierung weiter geht. Muss man eine Sortiermethode schreiben oder gibt es da nicht eine vordefinierte Methode .sort()?

 

[maki]

Collections.sort(..)

Abgesehen davon, könnte man die compare Methoide auch verkürzen, anstatt:

   public int compareTo (Point p){
      if( this.x < p.x )
            return -1;
        if( this.x > p.x )
            return 1;
           
        return 0;
   }

wäre auch das hier möglich:

   public int compareTo (Point p){
      return this.x - p.x;
   }

 

[kwonilchang]

Danke, jetzt funktioniert die Sortierung schonmal halbwegs.

Habe aber jetzt folgendes Problem:

Die Punkte sollen zuerst nach der x-Koordinate sortiert werden. Dies geht ja nun schon. Sollten jedoch Punkte mit der gleichen x-Koordinate eingegeben werden, so sollen diese Punkte nach der y-Koordinate in die Liste einsortiert werden.

Wenn ich nun einen dritten if-Fall verwende (this.x = p.x) erhalte ich eine Fehlermeldung "Can't match boolean to int". Steh anscheinend grad auf dem Schlauch... Eine zweite compareTo-Methode kann ich ja nicht einfach erstellen, da weiß das Programm ja nicht mehr, auf welche es zugreifen soll.

 

[Wildcard]

this.x == p.x

 

[kwonilchang]

Danke!

So funktioniert die Sortierung aber leider nicht:

public int compareTo (Point p){
		int ergebnis = 0;
		
		if (this.x < p.x)
			ergebnis = -1;
		
		if (this.x > p.x)
			ergebnis = 1;
		
		if (this.x == p.x)
			if (this.y < p.y)
				ergebnis = -1;
			if (this.y > p.y)
				ergebnis = 1;
			
			ergebnis = 0;
		
		
		return ergebnis;
	}

Liegt das an der Schachtelung?

 

[tfa]

Liegt das an der Schachtelung?

Mit Sicherheit. Benutze IMMER Blöcke in geschweiften Klammern bei if-Anweisungen!

 

[kwonilchang]

@ tfa: Danke für den Hinweis. Hatte diese Schreibweise schon ein paar Mal gesehen. Führt aber offensichtlich zu Fehlern.

public int compareTo (Point p){
		int ergebnis = 0;
		
		if (this.x < p.x){
			ergebnis = -1;
		}
		if (this.x > p.x){
			ergebnis = 1;
		}
		if (this.x == p.x){
			if (this.y < p.y){
				ergebnis = -1;
			}
			if (this.y > p.y){
				ergebnis = 1;
			}
			ergebnis = 0;
		}
		
		return ergebnis;
	}

Gebe ich jetzt Punkte ein, so wird mir die Liste so sortiert:

[(1, 5), (1, 2), (2, 3), (3, 4)]

Gleiche x-Koordinaten werden zwar erkannt, aber die y-Koordinaten nicht aufsteigend sortiert. Woran liegt das denn :bahnhof: ?

 

[maki]

Manchmal ist es ganz gut, Code zu vereinfachen.

if (this.x == p.x) {
return this.y - p.y;
} else {
return this.x - p.x;
}

 

[tfa]

Wenn die x-Koordinaten gleich sind, wird "ergebnis" immer auf 0 gesetzt. Das willst du bestimmt nicht.

 

[kwonilchang]

Danke, Sortierung ist jetzt richtig .