I wish to implement a hybrid algorithm that switches from insertion sort to merge sort once the input array size becomes too big.
This is my main function (I fixed my input array size at 30 currently as I wish to test my merge sort function) :
public static void main(String[] args) {
int[] a = genrandarray(30);
long bgn, end;
bgn = System.currentTimeMillis();
imsort(a, 0, a.length, 30);
end = System.currentTimeMillis();
for(int i = 1; i < a.length; i ){
if(a[i-1] > a[i]){
System.out.println("failed");
break;
}
}
System.out.println("milliseconds " (end-bgn));
}
Insertion sort is called when the array size is <20, else merge sort is called:
public static void imsort(int [] slot, int b, int e, int size) {
//if smaller than 20, use insertion sort
if (e-b<=20) {
insertionSort(slot, e); //e is the length of slot[]
System.out.println("imsort entered!");
}
else {
mergesort(b, e, slot);
System.out.println("mergesort entered!");
}
}
There is a Index 30 out of bounds error for my merge sort function currently.
public static int merge(int n, int m, int[] slot) {
int mid = (n m)/2;
int a = n, b = mid 1, i, tmp, cmp=0, comp=0;
//sanity check
if (m-n <= 0) return -1000;
while (a <= mid && b <= m) {
cmp = compare(slot[a], slot[b]);
comp ;
if (cmp > 0) { //slot[a] > slot[b]
tmp = slot[b ];
for (i = mid; i > a; i--)
slot[i] = slot[i-1];
slot[a ] = tmp;
}
else if (cmp < 0) //slot[a] < slot[b]
a ;
else {
//slot[a] == slot[b]
if (a == mid && b == m) break;
tmp = slot[b ];
a ;
for (i = mid; i > a; i--)
slot[i] = slot[i-1]; slot[a ] = tmp;
}
} // end of while loop;
return comp;
} // end of merge
public static int mergesort(int s, int e, int[] slot) {
//int comp =0;
int mid = (s e)/2;
int right=0, left=0;
if(e-s>0) {
//comp ;
left = mergesort(s,mid, slot);
//comp ;
right = mergesort(mid 1,e, slot);
}
return right left merge(s,e,slot);
}
I am unsure of the error in my merge / mergesort function. Can I get some further advice?
CodePudding user response：
a.length returns you 30 which is the length of your random array from the genrandarray method i believe. And your array is indexed 0 through 29. Try changing the main method like this and it will work out
public static void main(String[] args) {
int[] a = genrandarray(30);
long bgn, end;
bgn = System.currentTimeMillis();
imsort(a, 0, a.length-1, 30);
end = System.currentTimeMillis();
for(int i = 1; i < a.length; i ){
if(a[i-1] > a[i]){
System.out.println("failed");
break;
}
}
System.out.println("milliseconds " (end-bgn));
}
CodePudding user response：
First, let me congratulate on a very good post for someone new. You didn't post the line of code where the error is happening and code isn't complete, so I filled in some blanks and executed it:
import java.util.Arrays;
import java.util.Random;
public class Test {
public static int[] genrandarray(int n)
{
int[] a = new int[n];
Random r = new Random();
for(int i=0;i<n;i ) a[i] = r.nextInt();
return a;
}
public static void main(String[] args) {
int[] a = genrandarray(30);
long bgn, end;
bgn = System.currentTimeMillis();
imsort(a, 0, a.length, 30);
end = System.currentTimeMillis();
for(int i = 1; i < a.length; i ){
if(a[i-1] > a[i]){
System.out.println("failed");
break;
}
}
System.out.println("milliseconds " (end-bgn));
}
public static void imsort(int [] slot, int b, int e, int size) {
//if smaller than 20, use insertion sort
if (e-b<=20) {
Arrays.sort(slot, 0, e);
System.out.println("imsort entered!");
}
else {
mergesort(b, e, slot);
System.out.println("mergesort entered!");
}
}
public static int merge(int n, int m, int[] slot) {
int mid = (n m)/2;
int a = n, b = mid 1, i, tmp, cmp=0, comp=0;
//sanity check
if (m-n <= 0) return -1000;
while (a <= mid && b <= m) {
cmp = slot[a] - slot[b];
comp ;
if (cmp > 0) { //slot[a] > slot[b]
tmp = slot[b ];
for (i = mid; i > a; i--)
slot[i] = slot[i-1];
slot[a ] = tmp;
}
else if (cmp < 0) //slot[a] < slot[b]
a ;
else {
//slot[a] == slot[b]
if (a == mid && b == m) break;
tmp = slot[b ];
a ;
for (i = mid; i > a; i--)
slot[i] = slot[i-1]; slot[a ] = tmp;
}
} // end of while loop;
return comp;
} // end of merge
public static int mergesort(int s, int e, int[] slot) {
//int comp =0;
int mid = (s e)/2;
int right=0, left=0;
if(e-s>0) {
//comp ;
left = mergesort(s,mid, slot);
//comp ;
right = mergesort(mid 1,e, slot);
}
return right left merge(s,e,slot);
}
}
The error is caused by setting variable a to n in your merge function and then in the line cmp = slot[a] - slot[b]. Because arrays go from 0 to n-1, n will cause an out of bounds exception.