ArrayList sortieren mit Quicksort

[kwonilchang]

Hallo!

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:

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?

Danke schonmal!

Viele Grüße,

kwonilchang

 

[tfa]

Mit diesem Programm wird bisher jedoch nur die x- Koordinate allein richtig sortiert.

Sortiert ist gut. Du würfelst die Koordinaten aller Points völlig durcheinander.

Mit der .get()- Methode kann ich nicht auf das vollständige Punktobjekt zugreifen. Ich erhalte eine Fehlermeldung Can't match Point to int.

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.

 

[kwonilchang]

Hallo tfa!

Danke für die Antwort. Hatte ganz übersehen, int in Point umzuwandeln.

Hab das jetzt mal nachgeholt:

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?

 

[HLX]

       while (points.get(i) < pivot) i++; // Operator < undefined
       while (points.get(j) > pivot) j--; // Operator > undefined

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.

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.