[Java] Findet jemand den Fehler ?

[MasterOfWar]

Abend,
ich habe folgen Code für Mergesort

public void mergesort(int[] feld, int start,int end) {
		if(end-start<2){
			return;
		}
		
                int middle=(start+end)/2;
		mergesort(feld,1,middle);
		mergesort(feld,middle,end);
		
		int[] temp=new int[end-start];
		int left=start;
		int right=(start+end)/2;
		int j=0;
		while(j<end-start){
			if(left>=(middle){temp[j]=feld[right++];}else{
				if(right>=end){temp[j]=feld[left++];}else{
					if(feld[left]<feld[right]){temp[j]=feld[left++];}else{
						temp[j]=feld[right++];
					}
				}
				
			}
			j=j+1;
		}
		for(int i=0;i<end-start;i++){
			feld[i+start]=temp[i];
		}
	}

Wenn ich das mit der Reihe 7,8,9,1,2,44,56,0 teste bekomme ich 0,7,1,2,8,9,44,56 ,also nicht ganz das richtige.
Sieht zufällig jemand den Fehler ?

 

[CapFuture]

Ist grad bissel spät, aber ich würd folgendes zum debuggen empfehlen: Haltepunkt setzen und Einzelschritte machen um mal den Datenfluss zu beobachten. :/

 

[Alfadas]

Die erste Rekursion sollte mergesort(feld, start, middle) sein, denk ich und die zweite Rekursion sollte mergesort(feld, middle+1, end) sein.

Dann hast du glaub ich noch einen Fehler, da Java immer abrundet bei Divisionen.
Damit landet right bei 2 Elementen beim Zusammenfügen auf dem ersten Element und dieses wird mit sich verglichen, was falsch ist.

Ich kann dir auch den Debugger empfehlen.

 

[TheGenius]

Hier mal was das funktioniert vielleicht findest du den Fehler ja selber:

http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html

Kleiner Tipp noch:

generell solltest du dir angewöhnen deinen Code etwas zu kommentieren :-P ... erleichtert so manche Sache.

 

[Nexialist.]

public void mergesort(int[] feld, int start,int end)

Wie initialisierst du start und end? mit start=0 und end=feld.length-1?

 

[hubertus1990]

Probiers mal mit:

mergesort(feld,middle[B]+1[/B],end);

Falls du nur Code brauchst, hab ich vor 2 Tagen geschrieben:

public class MergeSort {

	/**
	 * STABLE SORT ALGORITHM
	 * mergeSort algorithm that sorts an array
	 * @param array
	 * @return the sorted array
	 */
	private static int [] mergeSort(int [] array) {
		
		if(array.length <= 1) return array;
		else {
			// calculate middle, needed to seperate
			int middle = array.length / 2;
			
			// separating the originating array into two parts (left and right of the middle)
			int [] left = new int[middle]; 
			int [] right = new int[array.length - middle];

			// filling the new arrays
			for (int i = 0; i < array.length - middle; i++) 	right[i] = array[i + middle];
			for (int i = 0; i < middle; i++) 					left[i] = array[i];

			left = mergeSort(left);
			right = mergeSort(right);
			
			return mergeArrays(left, right);
		}		
	}
	
	/**
	 * takes two parts of an array and sorts its values
	 * @param left
	 * @param right
	 * @return
	 */
	private static int [] mergeArrays(int [] left, int [] right) {
		
		// create a new array that will contain the sorted values
		int [] merged = new int[left.length + right.length];
		int iL = 0, iR = 0, iN = 0; // iL = index Left -> pointer to the first not sorted element in the left array, iN = index new (index in the new array where we are currently at)
		
		while(iL < left.length && iR < right.length) {
			if(left[iL] <= right[iR]) { // insert the smaller value first (change the <= to >= in order to reverse the sort)
				
				merged[iN] = left[iL];
				iL++; iN++;	// increase the pointers
			} else {
				merged[iN] = right[iR];
				iR++; iN++; // increase the pointers
			}
		}
		
		// inserting remainig left values
		while(iL < left.length) {
			merged[iN] = left[iL];
			iL++; iN++;		
		}
		
		// inserting remaining right values
		while(iR < right.length) {
			merged[iN] = right[iR];
			iR++; iN++;
		}
		
		// return the sorted array
		return merged;
	}
	
	/**
	 * method to print an array
	 * @param array
	 */
	private static void toString(int [] array) {
		
		for(int i = 0; i < array.length; i++) {
			System.out.print(array[i]+" ");
		}
		System.out.println();
	}
	
	/**
	 * main method to display the results
	 * @param args
	 */
	public static void main(String[] args) {
		
		System.out.println("MERGE SORT");
		
		// array that is mergesorted
		int [] array = new int[10];
		
		// filling the array with randomnumbers
		for(int i = 0; i < array.length; i++) array[i] = (int) (Math.random() * array.length);
		
		System.out.println("unsorted: ");
		toString(array);
		
		// use the mergesort to sort the array
		System.out.println("sorted: ");
		toString(mergeSort(array)); // sort the array and print it		
	}