Я пытаюсь реализовать алгоритм сортировки слиянием с некоторой оптимизацией, например, использовать временное хранилище только один раз и избегать копирования до последнего. Все в порядке, и многие тестовые файлы проходят, за исключением некоторых. В данном случае происходит несортированный массивАлгоритм показывает некоторые проблемы. Я написал операторы print в своем коде, пытаясь решить эту проблему, но не смог этого сделать. Поскольку многие тесты проходят, я считаю, что в программе нет ничего серьезного, просто она что-то пропускает.
Я пытался реализовать программу, и она во многих отношениях успешна, только 3 случая не проходят. Но главная проблема, с которой я сталкиваюсь, заключается в том, что контрольный пример Mergesort_two () не проходит, потому что егопросто. Это просто вызов двух номеров и утверждение в отсортированном виде, но моя программа это отрицает. Я считаю, что это небольшая ошибка, которую я не могу выяснить.
public static void mergesort(int[] input, int[] temp,
int start, int end,
boolean intoTemp) {
if (start == end) {
return;
}
if ((start + 1) == end) {
if (intoTemp == true) {
temp[start] = input[start];
return;
}
}
if (start < end) {
if (intoTemp == false) {
intoTemp = true;
int mid = (start + end)/2;
mergesort(input, temp, start, mid, intoTemp);
mergesort(input, temp, mid, end, intoTemp);
merge(input, temp, start, mid, end);
System.out.println("Input Array: " + Arrays.toString(input) +
" Temp: " + Arrays.toString(temp) + " intoTemp: " +
intoTemp + "Start Mid End: " + start + " " + mid + " " + end);
}
else if(intoTemp == true) {
intoTemp = false;
int mid = (start + end)/2;
mergesort(input, temp, start, mid, intoTemp);
mergesort(input, temp, mid, end, intoTemp);
merge(temp, input, start, mid, end);
System.out.println("Input Array: " + Arrays.toString(input) +
" Temp: " + Arrays.toString(temp) + " intoTemp: " +
intoTemp + "Start Mid End: " + start + " " + mid + " " + end);
}
}
if (start == 0 && end == input.length) {
System.arraycopy(temp, 0, input, 0, input.length);
}
}
/** Merges input[start...mid-1] with input[mid...end-1] into
* output[start...end-1]. The input array should not be modified at
* all, and only start...end-1 of the output array should be changed.
*
* @param input Input array
* @param output Output array
* @param start Starting index
* @param mid Midpoint index
* @param end Ending index+1
*/
public static void merge(int[] input, int[] output,
int start, int mid, int end) {
if (input == null || (start == mid && mid == end)) {
return;
}
int i = start;
int j = mid - 1;
int k = mid;
int index = start;
while (i <= j && k < end) {
if (input[i] <= input[k]) {
output[index] = input[i];
i++;
index++;
}
if (input[i] > input[k]) {
output[index] = input[i];
k++;
index++;
}
}
while (i <= j) {
output[index] = input[i];
index++;
i++;
}
while (k < end) {
output[index] = input[k];
index++;
k++;
}
}
}
////// TestЧехлы
@Test
public void testMergesort_Two() {
System.out.println("mergesort one element");
int[] array = new int[2];
// Already sorted
array[0] = 10; array[1] = 13;
CSSE240_Assign4.mergesort(array);
assertEquals(array[0], 10);
assertEquals(array[1], 13);
// Unsorted
array[0] = 3; array[1] = -4;
CSSE240_Assign4.mergesort(array);
assertEquals(array[0], -4);
assertEquals(array[1], 3);
}
@Test
public void testMergesort_Large() {
System.out.println("mergesort one large");
Random rng = new Random();
for(int s = 3; s < 20; ++s) {
int[] array = new int[s];
int[] orig = new int[s];
// Fill with random values.
for(int i = 0; i < s; ++i) {
array[i] = rng.nextInt();
orig[i] = array[i];
}
CSSE240_Assign4.mergesort(array);
Arrays.sort(orig);
// Make sure both arrays agree
for(int i = 0; i < s; ++i)
assertEquals(orig[i], array[i]);
}
}
@Test
public void testMergeInterleaved() {
// Various cases where the left/right halves are interleaved. We test
// this by picking a modulo m and moving all the elements where
// e % m < m/2 to the right side.
System.out.println("merge reverse sorted");
for(int s = 3; s < 20; ++s) {
int[] array = new int[s];
int mid = 0;
// Move the elements of the array around into the two halves.
for(int m = 2; m < 5; ++m) {
// Populate the array with 0...s-1
for (int i = 0; i < s; ++i) {
array[i] = i;
}
int[] left = new int[s];
int[] right = new int[s];
int lc = 0, rc = 0;
for(int i = 0; i < s; ++i)
if(array[i] % m < m/2)
right[rc++] = array[i];
else
left[lc++] = array[i];
// Copy back into the array
int j = 0;
for(int i = 0; i < lc; ++i)
array[j++] = left[i];
for(int i = 0; i < rc; ++i)
array[j++] = right[i];
mid = lc; // Midpoint
int[] output = new int[s];
Arrays.fill(output, -1);
// TODO: check different endpoints...
CSSE240_Assign4.merge(array, output, 0, mid, s);
for(int i = 0; i < s; ++i)
assertEquals(output[i], i);
}
}
}
testMergesort_Two Failed : expected <-4> but was <3>
testMergeInterleaved Failed: expected <0> but was <1>
testMergeSort_Large Failed : expected:<-1131373963> but was:<-2038582366>