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