Сверху вниз рекурсивный метод не работает и не уверен, как это исправить. Ява - PullRequest
Новая
       17

Сверху вниз рекурсивный метод не работает и не уверен, как это исправить. Ява

1 голос
/ 25 октября 2019

У меня проблема с домашним заданием для моего класса «Структура данных и алгоритм» - реализовать рекурсивную сортировку слиянием сверху вниз в Java. Продемонстрируйте, что ваша сортировка работает, генерируя случайную последовательность из 100 чисел, печатая их в необработанном несортированном виде, сортируя их, а затем распечатывая в отсортированном порядке.

И я немного кодировал, и это кажется правильным, но я получаю сообщение об ошибке и не могу понять, что я сделал не так. 

class RecursiveMergeSort
{
void TopDownMergeSort(int[] mainArray, int[] copyArray) // mainArray, copyArray, int n
{
    CopyArray(mainArray, copyArray);
    Split(copyArray, 0, 100, mainArray);
}

private void Split(int[] copyArray, int start, int end, int[] mainArray)
{
    if(end - start < 2)
    {
        return;
    }
    int middle = (end + start) / 2;
    Split(mainArray, start, middle, copyArray);
    Split(mainArray, start, end, copyArray);
    CombineArray(copyArray, start, middle, end, mainArray);
}

private void CombineArray(int[] mainArray, int start, int middle, int end, int[] copyArray)
{
    int s = start; //a
    int m = middle; //b

    for (int i = start; i < end; i++)
    {
        if(s < middle && (m >= end || mainArray[s] <= mainArray[m]))
        {
            copyArray[i] = mainArray[s];
            s = s + 1;
        }
        else
        {
            copyArray[i] = mainArray [m];
                    m = m + 1;
        }
    }

}

private void CopyArray(int[] mainArray, int[] copyArray)
{
    System.arraycopy(mainArray, 0, copyArray, 0, 100);
}

void UnsortedArray(int[] unsortedArray)
{
    for(int i = 0; i < unsortedArray.length; i++)
    {
        int random = (int)Math.floor(Math.random() * 100) + 1;
        unsortedArray[i] = random;
        System.out.println("\t" + i + unsortedArray[i]);
    }
}

void SortedArray(int[] unsortedArray)
{
    for(int i = 0; i < unsortedArray.length; i++)
    {
        System.out.println("\t: " + i + unsortedArray[i]);
    }
}
}

А вот драйвер: 

public class RecursiveDriver
{
public static void main(String[] args)
{
    int[] randomNumbers = new int[100];
    int[] sorted = new int[100];


    RecursiveMergeSort test = new RecursiveMergeSort();
    System.out.println("Unsorted Array:");
    test.UnsortedArray(randomNumbers);
    System.out.println("Sorted Array");
    test.TopDownMergeSort(randomNumbers, sorted);
    test.SortedArray(randomNumbers);
}
}

Это то, что я ожидаю:

Unsorted List: 100 61 8 76 51 89 30 63 11 1 4774 85 63 80 45 18 34 74 25 8 90 61 44 25 2 40 100 47 1 72 24 86 80 87 75 46 85 14 30 43 31 27 48 96 26 20 44 1 67 1 30 35 87 78 18 46 37 31 661 62 92 71 45 6 10 12 38 96 14 22 83 96 31 65 74 58 47 87 65 28 61 91 73 3 92 87 22 68 0 9 18 13 89 36 8 35 44

отсортированный список: 0 11 1 1 2 3 6 6 8 8 8 9 10 11 12 13 14 14 18 18 18 20 22 22 24 25 25 26 27 28 30 30 30 31 31 31 34 35 35 36 37 38 40 43 44 44 44 45 45 46 4647 47 47 48 51 58 61 61 61 61 62 63 63 65 65 67 68 71 72 73 74 74 74 75 76 78 80 80 83 85 85 86 87

И это результат, который я получаю, когда запускаю свой скрипт: Но я получаю:

Несортированный массив: 035 175 270 392 436 И это продолжается до тех пор, пока я не получу сообщение об ошибке: Исключение отсортированного массива в потоке "main" java.lang.StackOverflowError на RecursiveMergeSort.Split (RecursiveMergeSort. Java: 16) в RecursiveMergeSort.Split (RecursiveMergeSort.java:17) Вроде как-то связано со строкой 16/17, но я не совсем уверен, как это исправить. Спасибо за помощь.

1 Ответ

1 голос
/ 25 октября 2019 
    int middle = (end + start) / 2;
    Split(mainArray, start, middle, copyArray);
    Split(mainArray, start, end, copyArray);
    CombineArray(copyArray, start, middle, end, mainArray);

Должно быть 

    int middle = (end + start) / 2;
    Split(mainArray, start, middle, copyArray);
    Split(mainArray, middle, end, copyArray);
    CombineArray(copyArray, start, middle, end, mainArray);

Вы были очень близко, только начальный индекс второго рекурсивного вызова должен быть от среднего индекса до конца, а не от начала до самого концаснова (что приводит к ошибке переполнения стека)

С другой стороны - вы должны переименовать ваши методы в соответствии со стандартом, например: они начинаются со строчной буквы, такой как: 

private void combineArray(int[] mainArray, int start, int middle, int end, int[] copyArray)
...