Sortieren von Listen

[H26]

hey zusammen,

ich möchte den MergeSort Algorithmus für Listen von Comparables implementieren..den Algorithmus habe ich mehr oder weniger begriffen, doch ich weiss nicht ganz was Listen von Coparables sind. kann mir jemand helfen, damit diesen Algorithmus programmieren kann?

mfg

 

[HoaX]

Eben List<Comparable>, eine List (ArrayList, LinkedList, ...) die Objekte enthalten die das Interface Comparable implementieren.

 

[eRaaaa]

naja, beim sortieren musst du die elemente ja vergleichen können, damit du das kannst, müssen die klassen das comparable interface implementieren.

 

[H26]

ah oke, die objekte der Arraylist müssen Objekte sein, die das Interface Comparable implementiert haben..

 

[L-ectron-X]

die das Interface Comparable implementiert haben..

Das und sie müssen die compareTo()-Methode passend überschreiben. Also so, wie die Objekte sortiert werden sollen.

 

[H26]

ich habe die Klasse MergeSort darin will ich die zwei methoden merge und sort implementieren, wobei merge die rekursive hilfsmethode für die sort methode ist..ich weiss einfach nicht, wie mein konstruktor aussehen muss für mein oben geschildertes porblem..wäre dankbar, wenn mir jemand helfen könnte, damit ich mein programm fertigstellen kann...

public class MergeSort {
              //Konstruktor
              public MergeSort {
              
              }
              public static void sort (ArrayList<Comparable> list) {

              }

              public static int merge ( ) {

              }

}

 

[Illuvatar]

Wie dein Konstruktor aussehen soll, kann ich dir nicht sagen, das musst du selber wissen. Wenn deine sort-Methode statisch ist, dann macht es allerdings keinen Sinn einen Konstruktor zu haben - ich würde ihn private machen. Die merge-Methode könnte/sollte übrigens vermutlich auch private sein.
In dem Fall kann ich dir aber einen Tip für die sort-Methode geben: damit da was draus wird, muss die Signatur so in der Art aussehen:

public static <T extends Comparable<T>> void sort (List<T> list)

Was ich vermute, dass es besser wäre: erstelle ein

interface Sorter<T extends Comparable<T>>

. Dieses interface hat Methoden wie sort, setData und getData. [c]class MergeSort<T extends Comparable<T>> implements Sorter<T>[/c] ist dann eine konkrete Implementierung dieses interfaces. Dann kannst du zum Beispiel den Konstruktor haben:

public MergeSort(List<T> data)
{
  this.data = data;
}

 

[evil_kraudnsepp]

Ich hab eine Frage zum Thema Merge Sort. Ich bin Student an einer Fachhochschule. Bei einer Übungsaufgabe mussten wir Merge Sort implementieren. Die Musterlösung ist folgende:

	public static List mergeSort(List list, Comparator cmp) {
		if (list == null)
			return new ArrayList();
		if (list.size() <= 1)
			return list;
		
		List l1 = left(list); 				// linke Hälfte 
		l1 = mergeSort(l1, cmp);
		List l2 = right(list);                 // rechte Hälfte
		l2 = mergeSort(l2, cmp);
		List result = merge(l1, l2, cmp);  // sortierte Hälften mischen
		return result;
		
		// Lösung in einer Zeile
		// return merge(mergeSort(left(list),cmp),mergeSort(right(list),cmp),cmp);
	}

public static List merge(List liste1, List liste2, Comparator cmp) {

		int i1 = 0;
		int i2 = 0;

		List result = new ArrayList();

		while (i1 < liste1.size() && i2 < liste2.size()) {  // kleineren anfügen
			if (cmp.compare(liste1.get(i1), liste2.get(i2)) <= 0)
				result.add(liste1.get(i1++));
			else
				result.add(liste2.get(i2++));
		}
		// Rest anfügen
		while (i1 < liste1.size())
			result.add(liste1.get(i1++));

		while (i2 < liste2.size())
			result.add(liste2.get(i2++));

		return result;
	}

public static List left(final List list) {
		if (list == null || list.size()==0 )
			return list;
		return list.subList(0, list.size() / 2);
}

public static List right(final List list) {
		if (list == null || list.size()==0 )
			return list;
		return list.subList(list.size() / 2, list.size());
	}

Ich versteh nicht, wann der rekursive Aufruf von mergeSort wieder aufhört. Fehlt da nicht eine Abbruchbedingung?

 

[Marco13]

Das sind doch

        if (list == null)
            return new ArrayList();
        if (list.size() <= 1)
            return list;

?! (Für sowas kann man IMHO auch einen neuen Thread aufmachen)