Общая ошибка переполнения стека реализации Java в MergeSort - PullRequest
Новая
       7

Общая ошибка переполнения стека реализации Java в MergeSort

0 голосов
/ 13 ноября 2018

Я пытаюсь написать общий метод сортировки слиянием в Java.

Это мой исходный код: 

import java.util.ArrayList;
import java.util.List;

/**
 * An implementation of MergeSort
 *
 * @param <T> the type of data held by the array.
 */
public class MergeSort<T extends Comparable<? super T>> implements ArraySort<T>
{
    /**
     * Sort the array using a MergeSort.
     *
     * (recursively breaks down the array into sub arrays until arrays of size 1 are reached.)
     * (then works backwards merging these arrays back into each other until a sorted array state is reached containing
     *  all the elements of the initial unsorted array, but now sorted).
     *
     * @param array the array to be sorted.
     * @return array (sorted)
     */
    @Override
    public T[] sort(T[] array)
    {
        //If the array being sorted is less than 2 elements, it is already sorted and cannot be split into two separate
        //     arrays, so return the initial array to prevent an exception.
        if(array.length < 2)
        {
            return array;
        }

        //Create two sub arrays from the initial array passed in.
        T[] temp1 = copy(array, 0, (array.length/2) - 1);
        T[] temp2 = copy(array, (array.length/2), array.length - 1);

        //Sort these two arrays.
        sort(temp1);
        sort(temp2);

        //Merge the two subarrays back into the initial array.
        merge(array, temp1, temp2);

        //return the now sorted array.
        return array;
    }

    /**
     * Create and return a new array, comprised of a sublist of a passed in array.
     *
     * @param list the array to create the subarray from.
     * @param from the lower bound within list to copy.
     * @param to the upper bound within list to copy.
     * @return a new list comprised of the elements from 'from' to 'to' in 'list'
     */
    private <T> T[] copy(T[] list, int from, int to)
    {
        List<T> copyL = new ArrayList<>();
        for(int i = 0; i < to - from + 1; i++)
        {
            copyL.add(list[from + i]);
        }
        return copyL.toArray(list);
    }

    /**
     * Merge two sorted arrays into one larger array, keeping the sorted.
     *
     * @param target the array to merge source1 and source2 into.
     * @param source1 a sorted array
     * @param source2 a second sorted array.
     */
    private void merge(T[] target, T[] source1, T[] source2)
    {
        //Variables to keep track of the smallest unused element in each source array.
        int source1Index = 0;
        int source2Index = 0;

        //targetIndex keeps track of the next index to place the next smallest element into.
        for(int targetIndex = 0; targetIndex < target.length; targetIndex++)
        {
            //Choose the smallest element from the two source arrays to place into the target(sorted) array
            if(source1[source1Index].compareTo(source2[source2Index]) < 0)
            {
                target[targetIndex] = source1[source1Index];
                source1Index++;
            }
            else
            {
                target[targetIndex] = source2[source2Index++];
                source2Index++;
            }
        }
    }
}

Понятия не имею, почему, но я получаю ошибки StackOverflowкогда я вызываю строки 38 и 42. 

38 = T[] temp1 = copy(...) in the sort() method
42 = sort(temp1) in the sort() method.

Это заставляет меня поверить, что ошибка где-то в функции копирования, но я не знаю, как исправить проблему или найти решение.

Может кто-нибудь помочь мне исправить эту реализацию универсальной сортировки слиянием, пожалуйста?

StackTrace для сортировки массива из 12 элементов.

https://docs.google.com/document/d/1Ig5p7TZF_eX0Q_rroORnZUWnXtep7x-7cmDiSAZWlj8/edit?usp=sharing

Ответы [ 2 ]

0 голосов
/ 13 ноября 2018

Неправильно копируется ваш массив.

Использование: 

    private <T> T[] copy(T[] list, int from, int to) {
        return Arrays.copyOfRange(list, from, to);
    }

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

См. List.toArray (T [])

... Если список помещается в указанный массив, он возвращается в него.

т.е. вы копируете в исходный массив, а не создаете новый, поэтому размер ваших массивов никогда не уменьшается.

0 голосов
/ 13 ноября 2018

Ваши условия недостаточно хороши, вы получаете бесконечный вызов сортировки для ваших массивов.

По крайней мере, вы должны включить массив размером, равным 2: 

if(array.length <= 2)

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

В любом случае, скопируйте / вставьте полную трассировку стека, пожалуйста.

...