MergeSort mit Liste

[newbie2009]

Hey Leute ich brauch ma eure Hilfe, wir sollen MergeSort implementieren mit der Verwendung einer eigenen Klasse(einfach verkettete liste), die wir implementiert haben und die folgende Methoden hat:

public class Daten {

	DatenSatz kopf = new DatenSatz(1000000002);
	DatenSatz ende= new DatenSatz(1000000001);
	

	
		public Daten(){
			kopf.setNext(ende);
			ende.setNext(null);
			
		}
		
		
void vornanhängen(int k){
	DatenSatz neu = new DatenSatz(k);
	neu.setNext(kopf);// neu.next bekommt die referenz von kopf
	kopf=neu;


}

void deletefirst(){// löscht erstes element der liste
	kopf=kopf.getNext();


	
}
		
		
		
public void ausgeben(){ // gibt komplette liste aus
	DatenSatz aktuell= kopf;
	while(aktuell!=null){
		System.out.println(aktuell.lieferWert());
		aktuell=aktuell.getNext();
	}
	
}


void hintenanhängen(int j){ // hängt ein element ans ende der liste
	DatenSatz neu = new DatenSatz(j);
	DatenSatz help=neu;
	neu=kopf;
	
	while(neu.getNext()!=null){
		neu=neu.getNext();
	}
	
	ende.setNext(help);
	ende=help;
	
   
	
	
}

void listeerstellen(int anzahl){
	
	for(int i=0;i<anzahl-2;i++){
		int jo =( int)((Math.random()*100)+1);
		hintenanhängen(jo);
	}
	
	
}

Den MergeSort algorithmus verstehe ich, aber das auf Listen anzuwenden, bereitet mir Schwierigkeiten, ich weiß nicht so recht, wie ich die liste halbieren soll , mir fehlt da irgendwie der Ansatz.

 

[Landei]

Liste halbieren? Wie wäre es damit:
Kopf der Liste abschneiden, in Teilliste 1 packen
Kopf der Liste abschneiden, in Teilliste 2 packen
Kopf der Liste abschneiden, in Teilliste 1 packen
Kopf der Liste abschneiden, in Teilliste 2 packen
...

 

[newbie2009]

klingt logisch

also sagen wir mal wir haben 10 elemente in der liste,
dann erstelle ich 2 neue Teillisten und mache folgendes:


5 mal kopf abschneiden und packe diesen in die erste teilliste und 5 mal kopf abschneiden in die zweite teilliste ? oder eher abwechselnd?

 

[Final_Striker]

Also wenn du den Algorithmus versteht würdest, dann wäre dir klar, dass das egal ist. ;-)

 

[Landei]

Warum habe ich das wohl abwechselnd geschrieben? Ganz einfach: Weil man dann nicht mal die Länge der Liste kennen muss, beide Listen werden automatisch (soweit das möglich ist) gleichlang.

 

[newbie2009]

Warum habe ich das wohl abwechselnd geschrieben? Ganz einfach: Weil man dann nicht mal die Länge der Liste kennen muss, beide Listen werden automatisch (soweit das möglich ist) gleichlang.

ja habe aber eh noch eine methode, die die länge der liste bestimmt von daher ist es nich ausschlaggebend funzt auch so ^^.

static	void teillistenerstellen(Daten liste){
				
				Daten listehalb=new Daten();
				Daten listehalb2=new Daten();
			
				int j=liste.size(liste.kopf)/2;
				int z=liste.size(liste.kopf)-j;
				
				for(int i=0;i<j;i++){
					
					listehalb.hintenanhängen(liste.kopf.lieferWert());
					liste.deletefirst();
					
				}
				listehalb.deletefirst();
				listehalb.deletefirst();
				
				for(int zu=0;zu<j;zu++){
					
					listehalb2.hintenanhängen(liste.kopf.lieferWert());
					liste.deletefirst();
					
				}
				
					listehalb2.deletefirst();
					listehalb2.deletefirst();
				
					if(listehalb.size(listehalb.kopf)>0){
						teillistenerstellen(listehalb);
						}

					if(listehalb2.size(listehalb2.kopf)>0){
						teillistenerstellen(listehalb2);
					}
				
	
				
			}
			
			
			
			
		
}

könnte das so funzen ? oder ist der rekursive aufruf nicht ganz korrekt?

 

[Landei]

So würde ich es mit einer normalen Liste machen:

    public static <T extends Comparable<T>> List<T> sort(List<T> list) {
        if (list.size() <= 1) {
            return list;
        } else {
            List<T> one = new LinkedList<T>();
            List<T> two = new LinkedList<T>();
            while (!list.isEmpty()) {
                one.add(list.remove(0));
                if (!list.isEmpty()) {
                    two.add(list.remove(0));
                }
            }
            one = sort(one);
            two = sort(two);
            List<T> result = new LinkedList<T>();
            while (!(one.isEmpty() && two.isEmpty())) {
                result.add(one.isEmpty()
                        || (!two.isEmpty() && one.get(0).compareTo(two.get(0)) > 0)
                        ? two.remove(0) : one.remove(0));
            }
            return result;
        }
    }

 

[newbie2009]

puh so viele generics , muss ich die methode erstma nachvollziehen
aber danke

 while (!(one.isEmpty() && two.isEmpty())) {
                result.add(one.isEmpty() || (!two.isEmpty() && one.get(0).compareTo(two.get(0)) > 0)
                        ? two.remove(0) : one.remove(0));
            }
            return result;
        }

MM könntest du die anweisung vll bisschen erklären, ich verstehe den teil mit result.add(one.isEmpty()
nicht so wirklich.

danke im voraus

 

[Landei]

OK, das war vielleicht ein wenig zuviel zusammengeschrumpelt. Der ternäre Operator

a = bedingung ? b : c;

ist eigentlich nur eine Abkürzung für

if(bedingung) { a = b; } else { a = c; }

Er ist also sozusagen ein if-else, das einen Wert zurückgibt.

In der Schleife habe ich vier Fälle abzuhandeln (dass one und two leer sind, schließe ich ja schon von vornherein im while aus)
1) one ist leer -> nimm das erste Element von two
2) two ist leer -> nimm das erste Element von one
3) das erste Element von one ist kleiner als das von two -> nimm das erste Element von one
4) das erste Element von two ist kleiner als das von one -> nimm das erste Element von two

Meine Bedingung fasst die Punkte 1) und 4) zusammen, 2) und 3) sind dann der "else"-Zweig.

Über die Generics mach dir mal keinen Kopf. Im Prinzip sage ich mit <T extends Comparable<T>> nur: Ein Typ, der "vergleichbar" ist, also eine compareTo-Methode besitzt. Du kannst also mental überall wo T steht, einfach "String" oder "Integer" oder "Date" oder so einsetzen...