Generische Datentypen MergeSort

[bliko]

Ich habe eine Schnittstelle für verschiedene Sortieralgorithmen gebaut. Ich möchte nun den Algorithmus MergeSort, dem in der Grundstruktur Listen zugrunde liegen, in ein Array umwandeln und dann die bereits fertigen Methoden mergeSort bzw. merge aufrufen. Es kommen zwar keine Fehlermeldungen, doch sortiert wird auch nicht. Die beiden Methoden sind korrekt, wurden an anderer Stelle und in einem andeen Zusammenhang getestet, es liegt also nicht an deren Algorithmus, sondern wahrscheinlich an der Übergabe von irgendwelchen Parametern. Im folgenden nun die Dateien:

die Schnittstelle Sort

public interface Sort<E extends Comparable<E>> {
	public void sort(E[] sammlung);
}

die Klasse MergeSort;
damit sie der Schnittstelle entspricht, habe ich vorneweg die verlangte Methode sort geschrieben, die nichts anderes macht, als eine Liste in ein Array umzuwandeln um dann die Methode mergeSort aufzurufen. Dort liegt wahrscheinlich der Fehler, doch weiß ich nicht genau, wo, muss dort irgendetwas gecastet werden?

import java.util.*;

public class MergeSort<E extends Comparable<E>> implements Sort<E> {
	
	public void sort(E[] sammlung) {
		List<E> l = new Vector<E>();
		for (int i=0; i < sammlung.length; i++){
			l.add(sammlung[i]);
		}
		mergeSort(l);
	}
	
	public List<E> mergeSort(List<E> sammlung) {
		if (sammlung.size() <= 1)
				return sammlung;
		else {
			int laenge = sammlung.size();
			List<E> links = mergeSort(sammlung.subList(0, laenge/2));
			List<E> rechts = mergeSort(sammlung.subList(laenge/2, laenge)); //  
			if (links.size() == 0)
				return rechts;
			else if (rechts.size() == 0)
				return links;
			else { 
				List<E> ergebnis = new Vector<E>(); // hier wird zusätzlicher Platz verbraucht 
				merge(ergebnis, links.iterator(), rechts.iterator());
				return ergebnis;
			}
		}
	}
	
	
	public void merge(List<E> ausgabe,
			Iterator<E> eingabe1, Iterator<E> eingabe2) {
		E element1 = eingabe1.next(), element2 = eingabe2.next(); // erste Elemente
		while (true)
			if (element1.compareTo(element2) < 0) {
				ausgabe.add(element1); 
				if (eingabe1.hasNext())
					element1 = eingabe1.next(); 
				else {
					ausgabe.add(element2);
					break;
				}
			} else { // symmetrisch: eingabe1.compareTo(eingabe2) >= 0
				ausgabe.add(element2);
				if (eingabe2.hasNext())
					element2 = eingabe2.next();
				else {
					ausgabe.add(element1);
					break;
				}
			} 
		while (eingabe1.hasNext())
			ausgabe.add(eingabe1.next());
		while (eingabe2.hasNext())
			ausgabe.add(eingabe2.next());
	} // eine der beiden Schleifen ist leer
}

abschließend noch die Testklasse SortDemo.java

public class SortDemo {
	
	//static final ArrayList<String> al = new ArrayList(){}; 	
	private static final String testreihe = "EFACHBGD";

	static <E extends Comparable<E>> void sorttest(E[] sammlung, Sort<E> algorithmus){	
		System.out.println("Eingabe: ");
		for(E obj : sammlung){
			System.out.print(obj);
		}
		algorithmus.sort(sammlung);
		System.out.println("");
		System.out.println("Ausgabe: ");
		for(E obj : sammlung){
			System.out.print(obj);
		}
		System.out.print("\n");
	}	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Film[] filme = new Film[]{new Film("007","action", 200), new Film("Sissi", "kitsch", 100)};
		Character[] reihung = new Character[testreihe.length()];
		for (int i = 0; i < reihung.length; i++)
			reihung[i] = testreihe.charAt(i);
		System.out.println("BubbelSort<Character>:");
		sorttest(reihung, new BubbleSort<Character>());
		System.out.println("");
		/*
		System.out.println("BubbelSort<Film>:");
		sorttest(filme, new BubbleSort<Film>());
		*/
		System.out.println("MergeSort<Film>:");
		sorttest(filme, new MergeSort<Film>());
	}
}

das Ganze ist schon etwas komplex, aber vielleicht kann mir jemand weiterhelfen, danke im voraus.

 

[Marco13]

Ja, da wird eine neue Liste erstellt, und die wird dann sortiert - davon weiß der Array ja nix. Abhilfe...

public void sort(E[] sammlung) {
        List<E> l = new Vector<E>();
        for (int i=0; i < sammlung.length; i++){
            l.add(sammlung[i]);
        }
        mergeSort(l);

        // Nachher wieder (sortiert) in den Array schreiben:
        for (int i=0; i < sammlung.length; i++){
            sammlung[i] = l.get(i);
        }
    }

Ansonsten ... Nimm die Kommentare raus ... man findet sonst http://public.beuth-hochschule.de/~oo-plug/A&D/prog/kap561/MultiMerge.java :autsch:

 

[bliko]

Ja, da wird eine neue Liste erstellt, und die wird dann sortiert - davon weiß der Array ja nix. Abhilfe...

public void sort(E[] sammlung) {
        List<E> l = new Vector<E>();
        for (int i=0; i < sammlung.length; i++){
            l.add(sammlung[i]);
        }
        mergeSort(l);

        // Nachher wieder (sortiert) in den Array schreiben:
        for (int i=0; i < sammlung.length; i++){
            sammlung[i] = l.get(i);
        }
    }

 

[bliko]

ich habe nun die Änderung eingefügt, doch er sortiert noch immer nichts.

 

[Marco13]

Ach ja, er gibt auch noch eine Neue Liste zurück

public void sort(E[] sammlung) {
        List<E> l = new Vector<E>();
        for (int i=0; i < sammlung.length; i++){
            l.add(sammlung[i]);
        }
        [b]l = mergeSort(l);[/b] // Ergebnis von MergeSort als 'l' speichern

        // Nachher wieder (sortiert) in den Array schreiben:
        for (int i=0; i < sammlung.length; i++){
            sammlung[i] = l.get(i);
        }
    }

(es wird immer deutlicher, dass du das nicht selbst geschrieben hast )

 

[SlaterB]

von Testen kann ja auch keine Rede sein,
Lösung zu spät, aber fast noch wichtiger:

        System.out.println("list  vor: " + l);
        l = mergeSort(l);
        System.out.println("list nach: " + l);

(mit entsprechenden toString() in Film, sonst Ausgabe über Schleife)