Forum Mjukvara Programmering och digitalt skapande Tråd

MergeSort java, problem

1
Skriv svar
Permalänk
Medlem
●

MergeSort java, problem

Hej swec!
Jag håller på med en mergesort i java som fungerar löjligt långsamt och ibland inte alls. Kan nån titta på den och förklara varför?
Här är koden:

public class MergeSort{
    public static int[] sort(int[] x){
        if(x.length <= 1){
            return x;
        }
        int[] left = new int[(x.length/2)];
        int[] right = new int[(x.length/2)];
        int[] result = new int[(x.length)];
        int middle = (x.length/2);
        for(int a =0; a<=middle-1;a++){
            left[a]=x[a];
        }
        for(int b=0; b<=middle-1; b++){
            right[(b)]=x[middle+b];
        }
        left=sort(left);
        right=sort(right);
        result=merge(left, right);
        return result;
        
    }
    public static int[] merge(int[] left, int[] right){
        int[] result = new int[left.length+right.length];
        int leftpos =0;
        int rightpos=0;
        int resultpos=0;
        while(right.length >rightpos || left.length >leftpos){
            if(left.length >leftpos && right.length>rightpos){
                if(left[leftpos]<=right[rightpos]){
                    result[resultpos]=left[leftpos];
//                    System.out.println("result["+resultpos+"]= left["+leftpos+"]");
                    leftpos++;
                    resultpos++;
                }else{
                    result[resultpos]=right[rightpos];
//                    System.out.println("result["+resultpos+"]=right["+rightpos+"]");
                    rightpos++;
                    resultpos++;
                }
                
            }else if (right.length >rightpos){
                result[resultpos]=right[rightpos];
                resultpos++;
                rightpos++;
            }
        }
        return result;
        
    }
}

Tack på förhand.
/theWeasel

edit: La upp en gammal version först, fixat nu...

Senast redigerat
Redigera
Citera flera Citera
Permalänk
Medlem
●

Att det går långsamt är för att du gör väldigt många allokeringar under körningen, vilket är en dyr operation. Se http://en.wikipedia.org/wiki/In-place_algorithm.

Att den kraschar är för att du har minst nån bugg där i.

Varför gör du en egen merge sort till att börja med? Det finns färdiga sorteringsalgoritmer i Javas framwork (som dessutom är väldigt effektivt implementerade). Om du vill lära dig genom att implementera algoritmen själv skulle jag rekommendera att först läsa någon bra bok, t.ex. Introductions to Algorithms (http://mitpress.mit.edu/algorithms/).

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av VirtualIntent:

Att det går långsamt är för att du gör väldigt många allokeringar under körningen, vilket är en dyr operation. Se http://en.wikipedia.org/wiki/In-place_algorithm.

Att den kraschar är för att du har minst nån bugg där i.

Varför gör du en egen merge sort till att börja med? Det finns färdiga sorteringsalgoritmer i Javas framwork (som dessutom är väldigt effektivt implementerade). Om du vill lära dig genom att implementera algoritmen själv skulle jag rekommendera att först läsa någon bra bok, t.ex. Introductions to Algorithms (http://mitpress.mit.edu/algorithms/).

Gå till inlägget

Skolan, vi gör egna sorteringsalgoritmer, och min lärare rekommenderade att jag tittade på merge sort.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Testa med System.arraycopy så ska du se att iallafall uppdelningen går snabbare. Annars är det ju själva mergen som är det sega i mergesort.

I Java kan det ta en tredjedel av tiden med en iterativ lösning istället för rekursiv, fast de är ju inte lika kul eller snygga att skriva.

Visa signatur

I'm Winston Wolfe. I solve problems.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Har nu implementerat system.arraycopy, men det är inte direkt mitt problem. Har fortfarande inte hittat felet i koden som gör så att det går segt (jag menar alltså att det ibland tar runt 20 sek, inte att det går på ett par millisekunder).

Redigera
Citera flera Citera
Permalänk
Medlem
●

Jag orkade inte titta ordentligt på din utan skrev en variant som verkar fungera.

public static int[] sort(int[] list) {
	if (list.length > 1) {
		int middle = list.length / 2;
		int[] left = new int[middle];
		int[] right = new int[list.length - middle];
		System.arraycopy(list, 0, left, 0, left.length);
		System.arraycopy(list, middle, right, 0, right.length);
		list = merge(sort(left), sort(right));
	}
	return list;
}

public static int[] merge(int[] left, int[] right) {
	int[] list = new int[left.length + right.length];
	int lpos = 0;
	int rpos = 0;
	for (int i = 0; i < list.length; i++) {
		if (rpos == right.length || (lpos != left.length && left[lpos] < right[rpos]))
			list[i] = left[lpos++];
		else
			list[i] = right[rpos++];
	}
	return list;
}

Förhoppningsvis är det tillräckligt lika för att du ska kunna hitta vad felet är.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av VirtualIntent:

Jag orkade inte titta ordentligt på din utan skrev en variant som verkar fungera.

public static int[] sort(int[] list) {
	if (list.length > 1) {
		int middle = list.length / 2;
		int[] left = new int[middle];
		int[] right = new int[list.length - middle];
		System.arraycopy(list, 0, left, 0, left.length);
		System.arraycopy(list, middle, right, 0, right.length);
		list = merge(sort(left), sort(right));
	}
	return list;
}

public static int[] merge(int[] left, int[] right) {
	int[] list = new int[left.length + right.length];
	int lpos = 0;
	int rpos = 0;
	for (int i = 0; i < list.length; i++) {
		if (rpos == right.length || (lpos != left.length && left[lpos] < right[rpos]))
			list[i] = left[lpos++];
		else
			list[i] = right[rpos++];
	}
	return list;
}

Förhoppningsvis är det tillräckligt lika för att du ska kunna hitta vad felet är.

Gå till inlägget

Man tackar, den koden fungerar. Då jämför jag lite och skriver in lösningen senare.

Redigera
Citera flera Citera
1
Skriv svar
Senaste nyheterna
Hårdvara
Mjukvara
Övrigt
Nytt i forumet
Datorkomponenter
System
Ljud, bild och kommunikation
Spel och mjukvara