I've been working on a merge sort algorithm, which I want to use to sort a string array eventually.
The theory is that I sort an array containing the IDs that I want to sort in the same order as the main array which is a string, then sort the ID array and perform the same actions on the string array, theoretically sorting them both the same way.
For example, the array of ID values could be [1,2,3,4,5], and the main array would look something like ["Name, 1","Name, 2"]...
When I run the algorithm without including any of the second array parts it works correctly and this is the output:
[0, 1, 1, 10, 12, 16, 18, 24, 26, 53, 53, 53, 100]
But as soon as I try to add the second array operations, I get an exception saying:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
at s4001175.ct5057.flight.Booker.merge(Booker.java:250)
at s4001175.ct5057.flight.Booker.mergeSort(Booker.java:236)
at s4001175.ct5057.flight.Booker.mergeSort(Booker.java:232)
at s4001175.ct5057.flight.Booker.mergeSort(Booker.java:232)
at s4001175.ct5057.flight.FlightManagement.passengerStatus(FlightManagement.java:92)
at s4001175.ct5057.flight.FlightManagement.mainMenu(FlightManagement.java:53)
at s4001175.ct5057.flight.FlightManagement.main(FlightManagement.java:27)
Code:
public void mergeSort(int[] flightIDArr, int arrLength, String[] actualArr) {
// Flattened array of bookings to 1d array
String[] flatArray = flattenArray(readBookings());
// If array does not need to be split as length is already 1
if (arrLength < 2) {
return;
}
// Middle of the array
int mid = arrLength / 2;
//Left array of length of half of the array
int[] left = new int[mid];
// Other half of split array, with arrLength-mid size to ensure that it works even if the array is an odd length
int[] right = new int[arrLength - mid];
//Mirrored version of previous lines but for string array of what we actually want to sort (booking info)
String[] actualLeft = new String[mid];
// Same as above but right side
String[] actualRight = new String[arrLength - mid];
// for the elements in left array
for (int i = 0; i < mid; i ) {
// filling the left arrays with the info from the full array
left[i] = flightIDArr[i];
actualLeft[i] = flatArray[i];
}
// for elements in right array
for (int i = mid; i < arrLength; i ) {
// filling the right arrays with the info from the full array
right[i - mid] = flightIDArr[i];
actualRight[i - mid] = flatArray[i];
}
//recursively calls the mergesort algorithm to split the arrays as small as possible
mergeSort(left, mid, actualLeft);
mergeSort(right, arrLength - mid, actualRight);
//re merges the split arrays
merge(flightIDArr,actualArr, left, right, mid, arrLength - mid, actualLeft,actualRight);
}
//Method to merge all the split arrays
public void merge(
int[] flightIDArr, String[] actualArr, int[] leftArr, int[] rightArr, int left, int right, String[] actualLeft, String[] actualRight) {
//setting up variables for looping
int i = 0, j = 0, k = 0;
//
while (i < left && j < right) {
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k ] = leftArr[i ];
actualArr[k ] = actualLeft[i ];
}
else {
flightIDArr[k ] = rightArr[j ];
actualArr[k ] = actualRight[j ];
}
}
while (i < left) {
flightIDArr[k ] = leftArr[i ];
actualArr[k ] = actualLeft[i ];
}
while (j < right) {
flightIDArr[k ] = rightArr[j ];
actualArr[k ] = actualRight[j ];
}
// System.out.println(Arrays.toString(actualArr));
System.out.println(Arrays.toString(flightIDArr));
}
I've tried running through the program using the debugger in IntelliJ, and when the exception is produced to begin with at line 250, these are the values of the variables involved:
leftArr: 0:0
actualLeft:
0:
"Booking Number: 1
Flight Number: 000
Passenger Name: Test Name
Seat Number: 1
Seat Class: First"
So it looks like when this stage in the code is reached it is trying to set values in these arrays outside of their range, and yet this does not occur when running the algorithm without the second array involved, despite seemingly the same situation occurring on line 249, where
flightIDArr[k ] = leftArr[i ];
is called
Edit for new code:
Using the proposed answer I have changed my code, which seems to remove the error however the sorting no longer works correctly, and some numbers are noteven included:
The correct output:
[0, 1, 1, 10, 12, 16, 18, 24, 26, 53, 53, 53, 100]
Vs the current output with the new code:
[0, 1, 1, 1, 12, 16, 18, 18, 24, 53, 53, 53, 100]
As you can see there are now duplicate and missing values from the original dataset.
Code:
public void mergeSort(int[] flightIDArr, int arrLength, String[] actualArr) {
// Flattened array of bookings to 1d array
String[] flatArray = flattenArray(readBookings());
// If array does not need to be split as length is already 1
if (arrLength < 2) {
return;
}
// Middle of the array
int mid = arrLength / 2;
//Left array of length of half of the array
int[] left = new int[mid];
// Other half of split array, with arrLength-mid size to ensure that it works even if the array is an odd length
int[] right = new int[arrLength - mid];
//Mirrored version of previous lines but for string array of what we actually want to sort (booking info)
String[] actualLeft = new String[mid];
// Same as above but right side
String[] actualRight = new String[arrLength - mid];
// for the elements in left array
for (int i = 0; i < mid; i ) {
// filling the left arrays with the info from the full array
left[i] = flightIDArr[i];
actualLeft[i] = flatArray[i];
}
// for elements in right array
for (int i = mid; i < arrLength; i ) {
// filling the right arrays with the info from the full array
right[i - mid] = flightIDArr[i];
actualRight[i - mid] = flatArray[i];
}
//recursively calls the mergesort algorithm to split the arrays as small as possible
mergeSort(left, mid, actualLeft);
mergeSort(right, arrLength - mid, actualRight);
//re merges the split arrays
merge(flightIDArr,actualArr, left, right, mid, arrLength - mid, actualLeft,actualRight);
}
//Method to merge all the split arrays
public void merge(
int[] flightIDArr, String[] actualArr, int[] leftArr, int[] rightArr, int left, int right, String[] actualLeft, String[] actualRight) {
//setting up variables for looping
int i = 0, j = 0, k = 0;
//
while (i < left && j < right) {
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k] = leftArr[i];
actualArr[k ] = actualLeft[i ];
}
else {
flightIDArr[k] = rightArr[j];
actualArr[k ] = actualRight[i ];
}
}
while (i < left) {
flightIDArr[k] = leftArr[i];
actualArr[k ] = actualLeft[i ];
}
while (j < right) {
flightIDArr[k] = rightArr[j];
actualArr[k ] = actualRight[j ];
}
// System.out.println(Arrays.toString(ActualArr));
System.out.println(Arrays.toString(flightIDArr));
// System.out.println(" Actual Array: \n \n " (Arrays.toString (actualArr)));
}
CodePudding user response：
When you use k j etc. you increase the variable. You do this for both the left and the right array. But you probably only want to do it once, not twice.
You want to replace code like this:
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k ] = leftArr[i ];
actualArr[k ] = actualLeft[i ];
}
With this:
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k] = leftArr[i];
actualArr[k ] = actualLeft[i ];
}
Or this:
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k] = leftArr[i];
actualArr[k] = actualLeft[i];
k ; i ;
}