Habe eine ArrayList, in der Punkte abgespeichert sind (x- und y- Koordinaten).
Diese ArrayList möchte ich mittels Qicksort aufsteigend sortieren. Das habe ich bisher schon:
Code:
void quickSort(ArrayList <Point> points, int low, int high) {
// select middle element to split list
int pivot = points.get((low+high)/2).x;
// define markers i and j
int i = low;
int j = high;
// split array
while (i<=j) {
while (points.get(i).x < pivot) i++;
while (points.get(j).x > pivot) j--;
if (i<=j) {
int tmp = points.get(i).x;
points.get(i).x = points.get (j).x;
points.get(j).x = tmp;
i++;
j--;
}
} // the pivot element should now be in the right position
// recursion: sort the lists left and right of the pivot
if (j > low) quickSort(points, low, j);
if (i < high) quickSort(points, i, high);
}
Mit diesem Programm wird bisher jedoch nur die x- Koordinate allein richtig sortiert. Mit der .get()- Methode kann ich nicht auf das vollständige Punktobjekt zugreifen. Ich erhalte eine Fehlermeldung Can't match Point to int.
Kann mir jemand helfen, wie ich das komplette Punktobjekt sortieren kann?
Die tmp-Variable muss eben vom Typ Point sein und kein int. So einfach ist das. Aber wonach willst du denn sortieren? Nach der X-Koordinate?
Geht es dir darum, unbedingt Quicksort selbst programmieren zu wollen? Wenn nicht, kannst du auch Arrays.sort() mit einem Comparator benutzen. Ist zwar kein Quicksort, funktioniert aber auch.
Danke für die Antwort. Hatte ganz übersehen, int in Point umzuwandeln.
Hab das jetzt mal nachgeholt:
Code:
void quickSort(ArrayList <Point> points, int low, int high) {
// select middle element to split list
Point pivot = points.get((low+high)/2);
// define markers i and j
int i = low;
int j = high;
// split array
while (i<=j) {
while (points.get(i) < pivot) i++; // Operator < undefined
while (points.get(j) > pivot) j--; // Operator > undefined
if (i<=j) {
Point tmp = points.get(i);
points.get(i) = points.get (j); // linke Seite muss Variable sein
points.get(j) = tmp; //linke Seite muss Variable sein
i++;
j--;
}
} // the pivot element should now be in the right position
// recursion: sort the lists left and right of the pivot
if (j > low) quickSort(points, low, j);
if (i < high) quickSort(points, i, high);
}
Nun erhalte ich obige Fehlermeldungen. Bin mit Java noch nicht so vertraut; bin mir nicht sicher, ob das Sortieren noch ordentlich arbeitet, wenn ich einfach Variablen in das Programm einbaue.
Im Allgemeinen möchte ich für die Sortierung Quicksort verwenden. Die Punkte werden vom Benutzer frei eingegeben und sollen dann nach der x- Koordinate aufsteigend sortiert werden. Kommt eine x- Koordinate öfter vor, so soll anhand der y- Koordinate sortiert werden.
Kannst Du mir da noch einen Tipp zur Lösung geben?
Du kannst Objekte nicht einfach mit < > vergleichen, da es keine Definition dafür gibt. Du musst also erst festlegen, was im Fall von Point "größer als" oder "kleiner als" bedeutet. Dazu kannst du entweder einen Comparator schreiben, oder du müsstest Point ableiten und das Interface Comparable implementieren.
Code:
points.get(i) = points.get (j); // linke Seite muss Variable sein
points.get(j) = tmp; //linke Seite muss Variable sein
Das geht auch nicht. Du kannst mit get ein Objekt holen aber nicht modifizieren. Versuche nicht in der Ursprungsliste herumzuwurschteln. Erzeuge eine neue Liste und füge die Punkte sortiert dort ein.
