Javaでのマージソートの実装でエラーを見つけようとして、ここで脱毛が発生しています。
Input: 10 9 8 7 6 5 4 3 2 1
Output: 5 4 3 2 1 10 9 8 7 6
マージ関数で in between 配列を出力したところ、次のようになりました。
10 9 8 7 6 5 4 3 2 1
9 10
6 7
7 6 8
8 7 6 10 9
4 5
1 2
2 1 3
3 2 1 5 4
5 4 3 2 1 10 9 8 7 6
間違いは私のマージ機能にあるに違いないと確信しています。しかし、私はそれを見つけるのに本当に苦労しています。
これが私のコードです：
class merge1
{
//the array which will get sorted
static int N = 10;
static int[] A = new int[N];
static int[] cropArray(int[] a)
{
int[] b = new int[a.length-1];
System.arraycopy(a, 1, b, 0, b.length);
return b;
}
static int[] merge(int[] left, int[] right)
{
int[] merged = new int[left.length + right.length];
int i = 0;
//loop must go on until both arrays are emptied into merged
while(left.length > 0 || right.length > 0)
{
//first case: both arrays are still filled with elements to compare
if(left.length > 0 && right.length > 0)
{
if(left[0] <= right[0]) //check for the bigger one
{
merged[i] = left[0];
left = cropArray(left);
}
else
{
merged[i] = right[0];
right = cropArray(right);
}
}
else //second case: one of the arrays is empty
{
if(left.length > 0)
{
merged[i] = left[0];
left = cropArray(left);
}
else if(right.length > 0)
{
merged[i] = right[0];
right = cropArray(right);
}
}
i++;
} //while
printA(merged, merged.length);
return merged;
} //merge()
//merg sort recursivly splits the array in half until only one element is left and then merges each half back together in sorted order
static int[] mergeSort(int[] a)
{
//STEP 1
//exit case if only one element to sort return this element
if(a.length <= 1) return a;
//STEP 2
// split array into half
int len = a.length/2;
int[] left, right;
//check if length is even, if not even integer division will cause loss of data
if(a.length % 2 == 0)
{
//devide into two even halfs
left = new int[len];
right = new int[len];
}
else
{
//devide into two uneven halfs
left = new int[len];
right = new int[len+1];
}
//cycle through a and save out each half
//could also use System.arraycopy here as in the merge function
for(int i = 0; i < left.length; i++)
{
left[i] = a[i];
}
for(int i = 0; i < right.length; i++)
{
right[i] = a[i+len];
}
//split each half recursivley until only one element is left
mergeSort(left);
mergeSort(right);
//STEP 3
//merge sorted halfs and return
return merge(right, left);
} //mergeSort()
//initalizes the array for the worst case
//the worst case for merge sort is an array sorted in reverse
static void init()
{
int k = N;
for(int i = 0; i < A.length; i++)
{
A[i] = k;
k--;
}
}//init()
//prints the array, used to check if mergeSort is working
static void printA(int[] a, int n)
{
for(int i = 0; i < n; i++)
{
System.out.print(a[i] + " ");
}
System.out.println(); //break
} //printA
public static void main(String[] args)
{
//test code
init();
printA(A,A.length);
int [] sorted = mergeSort(A);
//printA(sorted, sorted.length);
/*//does 2000 sorts with arrays going from 0 to 1999 elements
for(int i = 0; i < 2000; i++)
{
init();
long x = System.nanoTime();
mergeSort(A, i);
System.out.println(i + " " + (System.nanoTime() - x));
}*/
} //main()
}//merge1