GenericMergeSort

[xite]

Hallo,

vorab ich hoffe ich habe das richtige Forum erwischt. Es geht um folgende Aufgabenstellung (in etwa):
- Eine Liste/Array o.ä. mit 10 Elementen vom Typ Eimer erstellen, diese sollen ein Zufallsvolumen haben
- Eimer muss Comparable implementieren
- Diese Liste soll mit einem generischen MergeSort sortiert werden

Mein Ansatz sieht wie folgt aus:
Eimer.java

public class Eimer implements Comparable<Object> {

	int volumen = 0;
	
	public Eimer(int value){
		this.volumen = value;
	}
	
	public int getVolumen(){
		return volumen;
	}
	
	public String toString(){
		return "Eimer mit Volumen: "+volumen;
	}

	public int compareTo(Object o) {
		Eimer other = (Eimer)o;
		if(this.getVolumen()<other.getVolumen()){
			return -1;
		} else if(this.getVolumen()>other.getVolumen()){
			return 1;
		}
		return 0;
	}

}

GenericMergeSort.java

import java.util.List;
import java.util.Vector;

public class GenericMergeSort<T extends List<?>> {
	public <E extends Comparable<?>> List<E> sort(List<E> list){
		if(list.size() <= 1){
			return list;
		} else {
			List<E> left = new Vector<E>();
			List<E> right = new Vector<E>();
			left = list.subList(0,list.size()/2);
			right = list.subList(list.size()/2,list.size());
		
			//rekursiver Merge Aufruf
			list = this.merge(this.sort(left),this.sort(right));
			System.out.println(list);
			
			return list;
		}
	}
	
	private <E extends Comparable<?>> List<E> merge(List<E> left, List<E> right){
		List<E> merge = new Vector<E>();
		System.out.println("Merge: ");
		
		while(left.size() > 0 && right.size() > 0){
			System.out.println("Vergleiche: "+left.get(0)+" und "+right.get(0));
			if(left.get(0).compareTo(right.get(0))) {
				merge.add(right.get(0));
				right.remove(0);
			} else {
				merge.add(left.get(0));
				left.remove(0);
			}
		}
		
		while(left.size() > 0){
			merge.add(left.get(0));
			left.remove(0);			
		}
		
		while(right.size() > 0){
			merge.add(right.get(0));
			right.remove(0);			
		}
		
		return merge;
	}
}

Main.java

import java.util.List;
import java.util.Vector;

public class Main {
	
	public static void main(String[] args){
		List<Eimer> list = new Vector<Eimer>();
		
		for(int i=0;i<10;i++){
			list.add(new Eimer((int)(Math.random()*50)));
		}
		
		System.out.println(list);
		
		// Merge-Sort
		GenericMergeSort<Vector<Eimer>> sorter = new GenericMergeSort<Vector<Eimer>>();
		list = sorter.sort(list);
		
		System.out.println(list);
	}
}

Leider funktioniert das ganze nicht so wie gewollt, als Fehler wird zurückgegeben:

Exception in thread "main" java.lang.Error: Unresolved compilation problem:
The method compareTo(capture#1-of ?) in the type Comparable<capture#1-of ?> is not applicable for the arguments (E)

at GenericMergeSort.merge(GenericMergeSort.java:28)
at GenericMergeSort.sort(GenericMergeSort.java:15)
at GenericMergeSort.sort(GenericMergeSort.java:15)
at GenericMergeSort.sort(GenericMergeSort.java:15)
at Main.main(Main.java:17)

Mit der Fehlermeldung kann ich leider absolut gar nichts anfangen und ich bin langsam echt am verzweifeln.
Hoffe es kann mir wer helfen.


Edit: Fehlermeldung hatte falsche Zeilenangeben -sry.

 

[Der Müde Joe]

>implements Comparable<Object>

implements Comparable<Eimer>

>E extends Comparable<?>

<E extends Comparable<? super E>> oder schlicht <E extends Comparable<E>>

ich hoffe, dass ich alle erwischt habe und richtig geschrieben ist (ungetestet)

 

[xite]

Hey ja, vielen Dank dass hat mich schon ein ganzes Stück weitergebracht

Leider wirft nun

		while(!left.isEmpty() && !right.isEmpty()){
			System.out.println("Vergleiche: "+left.get(0)+" und "+right.get(0));
			if(left.get(0).compareTo(right.get(0)) <= 0) {
				System.out.println(left.get(0)+" ist kleiner als "+right.get(0)+", left <= right");
				list.add(right.get(0));
				right.remove(0);
			} else {
				System.out.println(left.get(0)+" ist größer als "+right.get(0)+", left > right");
				list.add(left.get(0));
				left.remove(0);
			}
		}

eine ConcurrentModificationException. Soweit ich das jetzt verstanden habe kommt dies dadurchzustande, dass ich über left bzw right per while iteriere, die Listen aber innerhalb der Schleife verändere -richtig?

Was macht man dagegen am besten? Es ist ja der Sinn der Sache, dass die Listen in der Schleife verändert werden, damit sie irgendwann leer sind.

 

[Der Müde Joe]

>-richtig?

jup

>Was macht man dagegen am besten?

nicht modifizieren, wenn du darüber läufst, oder wirklich einen Iterator benutzen 8und dessen remove oder auf einer kopie der Liste arbeiten

 

[SlaterB]

subList liefert keine Kopie sondern nur eine Sicht, deshalb die Exception, Iteratoren gibts sonst ja nicht,

das new Vector() ist unnötig, wird durch die subList überschrieben,

entweder ein generische Parameter an der Klasse oder an den Methoden, beides zusammen ist unnötig,

mit noch paar Verbesserungen sieht folgendes ganz brauchbar aus:

public class Test
{

    public static void main(String[] args)
    {
        List<Integer> l = new ArrayList<Integer>();
        Collections.addAll(l, 4, 3, 552, 34, 433, 4);
        System.out.println("Start: " + l);
        l = new GenericMergeSort<Integer>().sort(l);
        System.out.println("End:   " + l);
    }
}


class GenericMergeSort<E extends Comparable<E>>
{
    public List<E> sort(List<E> list)
    {
        if (list.size() <= 1)
        {
            return list;
        }
        else
        {
            List<E> left = new ArrayList<E>(list.subList(0, list.size() / 2));
            List<E> right = new ArrayList<E>(list.subList(list.size() / 2, list.size()));

            // rekursiver Merge Aufruf
            list = this.merge(this.sort(left), this.sort(right));

            return list;
        }
    }

    private List<E> merge(List<E> left, List<E> right)
    {
        List<E> merge = new Vector<E>();
        System.out.println("Merge: " + left + " mit " + right);

        while (!left.isEmpty() && !right.isEmpty())
        {
            System.out.println("Vergleiche: " + left.get(0) + " und " + right.get(0));
            if (left.get(0).compareTo(right.get(0)) <= 0)
            {
                System.out.println(left.get(0) + " ist kleiner als " + right.get(0) + ", left <= right");
                merge.add(right.get(0));
                right.remove(0);
            }
            else
            {
                System.out.println(left.get(0) + " ist größer als " + right.get(0) + ", left > right");
                merge.add(left.get(0));
                left.remove(0);
            }
        }

        while (left.size() > 0)
        {
            merge.add(left.get(0));
            left.remove(0);
        }

        while (right.size() > 0)
        {
            merge.add(right.get(0));
            right.remove(0);
        }
        System.out.println("merge returnt " + merge);
        return merge;
    }
}

 

[xite]

vielen Dank euch beiden, jetzt läuft