# Wie sortiere ich diese Liste?



## huhu (11. Dez 2010)

Ich muss eine Methode zur Sortierung dieser Liste schreiben (ohne Java-Bibliotheksfunktionen zu nutzen):


```
public class RechteckListe {
   
   // Konstruktoren
   public RechteckListe() {
      first = null;
   }

   public RechteckListe(Rechteck r) {
      first = new RechteckElement(r);
   }
   
   /**
    * Testet ob die Liste leer ist
    * @return true falls die Liste leer ist
    */
   public boolean isEmpty() {
	   return (first == null);
   }
   
   /**
    * FÃ¼gt ein Rechteck vorne in die Liste ein
    * 
    * @param r Rechteck, welches zum neuen Kopf der Liste werden soll 
    */
   public void addFirst(Rechteck r) {
	   first = new RechteckElement(r, first);   
   }
   
   /**
    * Entfernt den Kopf der Liste
    * 
    * @return entferntes Rechteck, welches am Kopf der Liste stand
    */
   public Rechteck removeFirst() {
	   Rechteck result = null;
	   if (first == null) {
		   System.out.println("Warnung: removeFirst auf leere Liste angewandt!");
		   // removeFirst liefert in diesem Fall null zurÃ¼ck.
	   } else {
		   // Null-Pointer Exception ist hier ausgeschlossen, da first != null gelten muss.
		   result = first.getValue();
		   first  = first.getNext();
	   }
	   return result;
   }
   
   /**
    * Wie removeFirst(), ohne jedoch das Rechteck aus der Liste zu enternen
    *  
    * @return Rechteck, welches momentan am Kopf der Liste steht
    */
   public Rechteck readFirst() {
	   Rechteck result = null;
	   if (first == null) {
		   System.out.println("Warnung: readFirst auf leere Liste angewandt!");
		   // readFirst liefert in diesem Fall null zurÃ¼ck.
	   } else {
		   // Null-Pointer Exception ist hier ausgeschlossen, da first != null gelten muss.
		   result = first.getValue();
	   }
	   return result;
   }
   
   /**
    * HÃ¤ngt eine gegebene Liste von Elementen hinten an
    * 
    * @param l 
    *    Liste, welche hinten angehÃ¤ngt werden soll
    */
   public void append(RechteckListe l) {
	   if (first == null) {
		   first = l.first;
	   } else {
		   RechteckElement next = first;
		   while (next.getNext() != null) {
			   next = next.getNext();
		   }
		   next.setNext(l.first);
	   }
   }
   
   /**
    * Dreht die Reihenfolge der list um.
    */
   public void reverse() {
	   RechteckElement last = null;
	   RechteckElement current = first;
	   while (current != null) {
		   RechteckElement next = current.getNext();
		   current.setNext(last);
		   last = current;
		   current = next;
	   }
	   first = last;
   }
   
   /**
    * FÃ¼gt das Rechteck vor das erste grÃ¶ÃŸere Rechteck in die Liste ein
    * 
    * @param r Rechteck, welches geordnet eingefÃ¼gt werden soll.
    */
   public void insert(Rechteck r) {
	   if (first == null || r.isSmaller(first.getValue())) {
		   this.addFirst(r);
	   } else {
		   first.insertAfter(r);
	   }
   }
   
   /** 
    * Sortiert die Liste der GrÃ¶ÃŸe nach, wobei das kleinste Rechteck am Anfang steht.
    */
   public void sort() {
	   
	   // Meine Aufgabe

   }  
}
```

Die Elemente der Liste sind Rechtecke, die der Größe nach sortiert werden sollen (das kleinste soll zuerst kommen).
Die RechteckElementklasse schaut so aus:


```
public class RechteckElement {
	private RechteckElement next;
	private Rechteck value;
	
	public RechteckElement(Rechteck r) {
		value = r;
		next = null;
	}
	
	public RechteckElement(Rechteck r, RechteckElement n) {
		value = r;
		next = n;
	}

	/**
	 * @return the next
	 */
	public RechteckElement getNext() {
		return next;
	}

	/**
	 * @param next the next to set
	 */
	public void setNext(RechteckElement next) {
		this.next = next;
	}

	/**
	 * @return the value
	 */
	public Rechteck getValue() {
		return value;
	}

	/**
	 * @param value the value to set
	 */
	public void setValue(Rechteck value) {
		this.value = value;
	}
	
	public void insertAfter(Rechteck r){
		   if (next == null || r.isSmaller(next.getValue())) {
			   next = new RechteckElement(r, next);
		   } else {
			   next.insertAfter(r);
		   }
	   }
}
```

Ich verstehe die einzelnen Methoden der Klassen mehr oder weniger, und Arrays kann ich mit Bubblesort oder Selection sort sortieren, aber bei dieser Aufgabe bin ich trotzdem irgendwie überfragt. Kann mir jemand einen Tipp geben wie das geht/ wie ich anfangen soll?


----------



## huhu (12. Dez 2010)

mir fällt nur ein dass ich damit das erste Objekt entfernen und dann sortieren kann, glaube ich:


```
this.insert(removeFirst());
```

ansonsten fällt mir irgendwie nichts ein 
Wie durchläuft man die Liste damit alle Objekte sortiert werden?


----------



## XHelp (12. Dez 2010)

Sind irgendwelche Bedingungen an der Sortieren gestellt? Hauptsächlich in situ oder ex situ.
Wenn nicht, dann kannst du doch eine neue Liste erstellen:

```
durch die ganze Liste laufen:
- kleinstes Element raussuchen
- in ans Ende der neuen Liste packen
- aus der ursprünglichen Liste löschen
```


----------



## huhu (12. Dez 2010)

Besondere Bedingungen sind nicht gestellt, nein.
Dieses Testprogramm muss halt dann korrekt ablaufen:


```
import java.awt.Color;
import java.awt.Graphics2D;
import java.util.Random;

/**
 * Demonstriert die Verwendung einer verketten Liste von Rechtecken.
 * 
 * @author jost
 * 
 */

public class ListDemo {
	// Eckdaten der Grafik
	private static final int xsize = 500;
	private static final int ysize = 500;
	// Initalisierung von Grafik und Zufallsgenerator
	private static Random random = new Random();
	private static CanvasFrame frame = new CanvasFrame("ListDemo", xsize, ysize);
	private static Graphics2D canvas = frame.getGraphics();

	/**
	 * Demonstriert die Verwendung einer verketten Liste von Rechtecken.
	 * 
	 * @param args
	 *            Wird ignoriert
	 * 
	 */
	public static void main(String[] args) {
		RechteckListe rl = generateExample();
		rl.sort(); // VervollstÃ¤ndigen Sie die Methode sort in der Klasse RechteckListe
		rl.reverse();
		while (!rl.isEmpty()) {
			drawRechteck(rl.removeFirst());
			int rdm = 55 + random.nextInt(55);
			frame.sleep(rdm);
		}
		// Fenster schliessen
		frame.waitMouseClicked();
		frame.dispose();
	}

	/**
	 * Zeichnet ein Rechteck in einer zufÃ¤lligen Farbe
	 * 
	 * @param ob
	 *            Rechteck to be drawn
	 */
	public static void drawRechteck(Rechteck r) {
		Color color;
		if (true) { // WÃ¤hle: true->Feste Farbe; false->Zufallsfarbe
			// Abgespeicherte Farbe aus Rechteck:
			color = new Color(r.getColor());			
		} else {
			// Zufallsfarbe:
			int maxcolor = 1 << 24; // Maximaler Farbwert 2^24
			color = new Color(random.nextInt(maxcolor));
		}
		canvas.setColor(color);
		Punkt ll = r.getUpperLeft();
		canvas.fillRect(ll.getX(), ll.getY(), r.getWidth(), r.getHeight());
		frame.repaint();
	}

	/**
	 * Generiert ein Liste von verschiedenen Rechtecken.
	 * 
	 * @return Liste von verschiedenen Rechtecken
	 */
	public static RechteckListe generateExample() {
		RechteckListe result = new RechteckListe();
		int scale = 5;
		for (int i = 0; i * scale < xsize || i * scale < ysize; i += 3) {
			result
					.addFirst(new Rechteck(i * scale, i * scale, xsize
							- (i * scale * 2), ysize - (i * scale * 2),
							(i + 44 << 17)));
		}
		result.reverse();
		for (int i = 1; i * scale < xsize || i * scale < ysize; i += 3) {
			result
					.addFirst(new Rechteck(i * scale, i * scale, xsize
							- (i * scale * 2), ysize - (i * scale * 2),
							(i + 14 << 10)));
		}
		result.reverse();
		for (int i = 2; i * scale < xsize || i * scale < ysize; i += 3) {
			result.addFirst(new Rechteck(i * scale, i * scale, xsize
					- (i * scale * 2), ysize - (i * scale * 2), (i + 14 << 2)));
		}
		result.reverse();
		return result;
	}
}
```


----------



## XHelp (12. Dez 2010)

Ja, dann kannst du auch einfach eine neue Liste erstellen und dann die als first in deine alte setzen.


----------



## huhu (12. Dez 2010)

Ich komm schon bei deinem ersten Punkt nicht weiter.
Was mich verwirrt ist dass die Größe vom Typ Rechteck ist (In der Klasse RechteckElement das value vom Typ Rechteck).
Nun weiß ich nicht wie ich das kleinste Element in der Liste finde.
Wenn der Typ int wäre würde ich es so machen:

int MinElement = unendlich;
int IndexvomkleinstenElement = 0;

for (i = 0; i < Listenlänge; i++){
if (jetziges Element < Minelement){
Minelement = jetzigesElementGröße;
IndexvomkleinstenElement = i;
}


Nun habe ich ich das Problem dass das leider keine int sind, was muss ich da verändern? Aus der Methode insert() hab ich herausgelesen dass man für Größenvergleiche zB.  
	
	
	
	





```
r.isSmaller(first.getValue())
```
 hernehmen kann.
Habe aber eben das Problem:
1) wie setzt man "MinElement" auf unendlich wenn es vom Typ Rechteck ist
2) wie finde ich die Listenlänge heraus

ich bin einfach komplett überfragt bei der Aufgabe


----------



## XHelp (12. Dez 2010)

Vllt solltest du compareTo-Methode implementieren. Wie stellst du denn ein Rechteck dar? Du kannst ja den Umfang vergleichen oder so.


----------



## huhu (12. Dez 2010)

Ach oben hab ich das Beispiel etwas falsch geschrieben, so würde das ungefähr ausschauen glaub ich wenn ich es mit dem Typ int machen würde:


int MinElement = first.getValue();
int IndexvomkleinstenElement = 0;

for (i = 0; i < Listenlänge; i++){
first.getNext();
if (jetziges Element < Minelement){
Minelement = jetzigesElementGröße;
IndexvomkleinstenElement = i;
}

... oder so ähnlich

dann wüsste ich schonmal an welcher Stelle das Teil steht, aber da denke ich schon wieder in Arrays, wie macht man das bei Listen, hmmhhm


----------



## XHelp (12. Dez 2010)

Naja, so als Pseudocode kann es, glaube ich, stehen bleiben. Aber du kannst ja die Objekte nicht mit "<" vergleichen. Deswegen ja der Tipp mit compareTo


----------



## huhu (12. Dez 2010)

Ach moment, ich hatte die Klasse Rechteck selber irgendwie komplett vergessen, ich Idiot wollte den Typ Rechteck miteinander vergleichen, derweil haben die Rechtecke selber ganz normale int variablen die ich vergleichen kann, ja den Umfang kann ich vergleichen, moment ich bastle mir mal etwas zusammen


----------



## huhu (12. Dez 2010)

Das compareTo brauche ich glaub ich nicht, denn ich habe bereits:


```
r.isSmaller(first.getValue())
```
 um Rechtecke zu vergleichen. Dann brauche ich auch nicht die Werte/Umfang der Rechtecke glaube ich nicht, weil ich sowieso diese Methode habe oder? Aber ich weiß trotzdem nicht wie ich meinen oberen Pseudocode richtig in Java umformuliere.


----------



## huhu (12. Dez 2010)

Außerdem habe ich ja folgende Methode, die muss bestimmt auch für etwas gut sein:


```
/**
    * FÃ¼gt das Rechteck vor das erste grÃ¶ÃŸere Rechteck in die Liste ein
    * 
    * @param r Rechteck, welches geordnet eingefÃ¼gt werden soll.
    */
   public void insert(Rechteck r) {
	   
	   if (first == null || r.isSmaller(first.getValue())) {
		   this.addFirst(r);
	   } else {
		   first.insertAfter(r);
```

Könnte man damit nicht irgendwas machen?


----------



## XHelp (12. Dez 2010)

sofern deine insertAfter-Methode nach dem ähnlichem Prinzip funktioniert würdest du dann ständig eine Liste bekommen, die bereits sortiert ist. Dann wäre .sort() überflüssig. Ich denke also nicht, dass es Sinn der Aufgabenstellung ist.


----------



## huhu (12. Dez 2010)

Ich mein die hier hab ich um Rechtecke zu vergleichen:


```
/**
	 * Vergleicht den FlÃ¤cheninhalt zweier Rechtecke
	 * 
	 * @param r
	 *            Ein Rechteck
	 * 
	 * @return True, falls das Ã¼bergebene Rechteck r grÃ¶ÃŸer ist
	 */
	public boolean isSmaller(Rechteck r) {
		return (r.area() > this.area());
	}
}
```

sry hab etwas chaotisch geschrieben, ich melde mich mal an sodass ich ältere Beiträge ab jetzt bearbeiten kann


----------



## huhu (12. Dez 2010)

Die insert() Methode nimmt das erste Rechteck und sortiert es. Ich soll die ganze Liste sortieren. Ich kann dann zB. die insert() Methode über jedes Rechteck laufen lassen oder so ähnlich, nur weiß ich nicht wie man das anstellen könnte. Oder deine Version ist natürlich auch gut, aber ich weiß nicht genau wie ich das kleinste Rechteck finde, siehe meine Probleme oben.


----------



## huhu (12. Dez 2010)

* ich mein ein beliebiges Rechteck das über die Parameter gegeben wurde


----------



## XHelp (12. Dez 2010)

Du weißt nicht wie du Rechtecke vergleichst, hast aber schon eine isSmaller-Methode? oO


----------



## huhu (12. Dez 2010)

nein die ist bereits gegeben, hab sie anfangs nur irgendwie übersehen


----------



## huhu (12. Dez 2010)

also was für nützliche Methoden bereits gegeben sind:

Bei der Liste:
isEmpty() prüft ob die Liste leer ist
addFirst(Rechteck r) fügt das Rechteck an den Anfang
readFirst() liest das erste Rechteck aus
insert(Rechteck r) ordnet r vor das erste größere Rechteck
removeFirst() entfernt das erste Rechteck
append(RechteckListe l) hängt eine gegebene Liste von Elementen hinten an

Beim Rechteck:
isSmaller(Rechteck r) vergleicht ob dieses Rechteck kleiner ist als das gegebene

Beim RechteckElement:
getNext() kommt zum nächsten RechteckElement
getValue() gibt das Rechteck aus

hmm das waren alle wichtigen, hätte ich vermutlich am Anfang schon herausschreiben sollen


----------



## XHelp (12. Dez 2010)

Hm. deine Liste ist aber immer sortiert, weil insert-Methode es bereits sortiert einfügt....


----------



## huhu (12. Dez 2010)

Nur wenn ich die Rechtecke über die Insert Methode einfügen würde, aber ich hab sozusagen bereits eine unsortierte Liste gegeben und soll sie sortieren. Dabei kann ich aber natürlich auch die insert Methode irgendwie verwenden.


----------



## huhu (12. Dez 2010)

Hm dann mach ich einfach eine neue Liste, und füge die Rechtecke der alten Liste mit insert in die neue Liste und hänge dann mit append() die neue Liste an die alte Liste sobald sie leer ist (prüfen mit isEmpty Methode). Müsste doch so gehen oder? Ich schau mal ob ichs hinbekomm. Dann brauch ich garnicht das kleinste Element finden, weil die insert Methode alles für mich übernimmt.


----------



## huhu (12. Dez 2010)

ok habs 

ist eigentlich viel simpler als ich dachte, ich hätt mir gleich alle Methoden herausschreiben sollen. Dein Tipp mit einer neuen Liste die man dann an die alte dranhängt ist aber auch gut gewesen.

Danke


----------

