# Collection Sort



## SideWinder (23. Feb 2008)

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 (24. Feb 2008)

Übergib einen Comparator


----------



## Guest (24. Feb 2008)

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 (24. Feb 2008)

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


----------



## Beni (24. Feb 2008)

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


----------



## tincup (24. Feb 2008)

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 (25. Feb 2008)

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 (25. Feb 2008)

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 (25. Feb 2008)

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 (25. Feb 2008)

this.x == p.x


----------



## kwonilchang (25. Feb 2008)

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 (25. Feb 2008)

kwonilchang hat gesagt.:
			
		

> Liegt das an der Schachtelung?


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


----------



## kwonilchang (26. Feb 2008)

@ 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 (26. Feb 2008)

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 (26. Feb 2008)

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


----------



## kwonilchang (26. Feb 2008)

Danke, Sortierung ist jetzt richtig   .


----------

