dimanche 3 mai 2015

Merge Sort Not Working Java

This merge sort algorithm fails because an ArrayIndexIsOut of bounds.

public static int[] mergeSort(int[] toBeSorted) {
    //If there is only one item in the array, and it is said to be sorted
    if (toBeSorted.length <= 1){
        return toBeSorted;
    }

    //find the indexes of the two sub-groups
    int[] left = new int[toBeSorted.length/2];
    int[] right = new int[toBeSorted.length-left.length];
    //Fill each sub-group with the correct numbers
    //Starting with the left group
    for(int i = 0; i <= left.length - 1; i++){
        left[i] = toBeSorted[i];
    }
    //Then the right group
    for(int i = left.length - 1; i <= toBeSorted.length - 1; i++){
        right[i] = toBeSorted[i];
    }


    //Merge sort each sub-group
    mergeSort(left);
    mergeSort(right);

    //Merge the two sub-groups
    toBeSorted = merge(left, right);

    return toBeSorted;
}

//Merging method
public static int[] merge(int[] left, int[] right){
    //Answer array
    int[] merged = new int[left.length + right.length];
    //Next index to check in each array
    int lCursor = 0;
    int rCursor = 0;
    //Next index to place numbers into answer
    int mergedCursor = 0; 

    //The merging part:
    //If there are still items to merge, then do so
    while(mergedCursor != merged.length){
        //left index is empty
        if(lCursor == left.length) {
            merged[mergedCursor] = right[rCursor];
            //increment the correct cursors
            rCursor += 1;
            mergedCursor += 1;
        }
        //right index is empty
        else if(rCursor == right.length) {
            merged[mergedCursor] = right[lCursor];
            //increment the correct cursors
            lCursor += 1;
            mergedCursor += 1;
        } 
        //Left side is smaller
        else if(left[lCursor]<right[rCursor]){
            merged[mergedCursor] = left[lCursor];
            //increment the correct cursors
            lCursor += 1;
            mergedCursor +=1;
        }
        //Right side is smaller
        else if(right[rCursor]<left[lCursor]){
            merged[mergedCursor] = right[rCursor];
            //increment the correct cursors
            rCursor += 1;
            mergedCursor +=1;
        }
    }
    //return the merged output
    return merged;
}

The line inside the for loop assigning numbers to the right array is where the problem is, but I can't tell why. Also, originally I had i = left.length in that for loop, but that was causing the entire right array to be set to zeros.

Can any of you help me?

Aucun commentaire:

Enregistrer un commentaire