Eine ArrayList effizient sortieren

[Guest]

Moin,

ich hoffe ihr könnt mir helfen. Ich habe ein kleines Javaprojekt, bei dem ich mit sortierten ArrayListen arbeiten muss. Die Elemente werden dabei nach dem Datum sortiert. Bisher sieht meine funktionierende Methode so aus:

private ArrayList<Game> sortGames(ArrayList<Game> gList) {
	for (int i=0; i< gList.size();i++){
	    for (int j=0; j<gList.size();j++){
		if (gList.get(i).getDay().before(gList.get(j).getDay())){
		    Game bGame = gList.get(i);
		    gList.set(i, gList.get(j));
		    gList.set(j, bGame);
		}
	    }
	}
	return gList;
    }

Das Problem ist nur, dass diese Sortiermethode ein ziemliches Bottleneck darstellt. Ist ja auch klar. Es ist ein quadratischer Algorithmus, der auf jedes Element der Liste auch noch manuell zugreifen muss. Deshalb würde ich gerne wisen, ob es eventuell in Java eine effizientere Möglichkeit gibt, diese verdamte Liste sortiert zu bekommen.

[/code]

 

[Beni]

Schau dir die Methode "sort" der Klasse "Collections" an, und den "Comparator" der zwei Element vergleicht.

Ich glaub, das hatten wir schon ein- oder zweimal irgendwo im Forum :bae:

[Edit: achja, in der FAQ hatten wir das ja auchnoch]

 

[siroFranz]

würde das auch mit BubbleSort gehn oder ähnlichen Verfahren?

 

[Marco13]

Der Bottleneck IST vermutlich gerade das BubbleSort. Wie man "nicht-manuell" auf die Elemente zugreifen soll, weiß ich gerade nicht. Vielleicht gibt es auch nocht was effizienteres als "getDay().before(...getDay()). Wenn man die Zeit als "int" speichern würde, wäre der Vergleich vmtl. schneller.
Collections.sort verwendet glaubich einen optmierten Quicksort oder sogar ein MergeSort, dürfte also schon bei "relativ kleinen" Listen deutlich schneller sein.

 

[Guest]

Hallo
zum Thema ArrayList sortieren habe ich auch eine Problem. Und zwar möchte ich mehrere Koordinatenpunkte in einer ArrayList abspeichern. Danach möchte ich diese nach x-Werten sortieren. Ich habe versucht das im untenstehenden Code zu verwirklichen, bekomme aber beim Compilieren eine Menge von Fehlern die ich mir auch nach längerem rumprobieren und überlegen nicht erklären kann. Es wäre nett wenn da mal jemand drübersehen könnte und mir sage wo mein Fehler ist.

import java.util.*;

class Point {
	
	double posx;
	double posy;
	Point(double x, double y){
		posx = x;
		posy = y;
	}
	double getX(){
		return posx;
	}
}

class Skyline1 {
	
	public SortXWerte implements Comperator<Point> {
		int compare(Point a, Point b) {
			return a.getX() - b.getX();
		}
	}
	
	public static void main(String args[]) {
		ArrayList<Point> points = new ArrayList<Point>();
		
		points.add(new Point(2.5, 4.0));
		points.add(new Point(3.0, 5.0));
		points.add(new Point(3.5, 4.0));
				
		Collections.sort(points, new SortXWerte());
	}
}

 

[SlaterB]

was soll

public SortXWerte implements Comperator<Point> {
int compare(Point a, Point b) {
return a.getX() - b.getX();
}
}

sein, eine Klasse?
wie kann man eine Klasse ohne das Schlüsselwort 'class' defininieren?