Ошибка переполнения стека при общем сопоставимом алгоритме сортировки слиянием - PullRequest
Новая
       28

Ошибка переполнения стека при общем сопоставимом алгоритме сортировки слиянием

1 голос
/ 26 мая 2019

Я получаю сообщение об ошибке переполнения стека при вызове слияния в моем методе сортировки.Это, вероятно, быстрое решение, но я не могу думать ни о чем в данный момент.Пожалуйста, просмотрите мой код. 

public class MergeSorter {

    public static <T> void sort(Comparable<? extends T>[] items) {
        if (items == null) {
            throw new IllegalArgumentException("Item is null.");
        }
        mergeSort(items, 0, items.length - 1);
    }

    @SuppressWarnings("unchecked")
    private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {
        if(begIndx == endIndx) {
            return;
        }
        if(items.length > 1) {
            int midIndx = items.length / 2;
            mergeSort(items, begIndx, midIndx);
            mergeSort(items, midIndx + 1, endIndx);
            merge(items, begIndx, midIndx, endIndx);
        }
    }

    @SuppressWarnings("unchecked")
    private static <T> void merge(Comparable<? extends T>[] array, int begIndx, int midIndx, int endIndx) {
        int sizeOfLeft = midIndx - begIndx + 1;
        int sizeOfRight = endIndx - midIndx;

        /// change to generic later
        @SuppressWarnings("unchecked")
        T[] leftArr = (T[]) new Object[sizeOfLeft + 1];
        @SuppressWarnings("unchecked")
        T[] rightArr = (T[]) new Object[sizeOfRight + 1];

        for (int i = 0; i <= sizeOfLeft; i++) {
            leftArr[i] = (T) array[begIndx + i];
        }
        for (int j = 0; j <= sizeOfRight; j++) {
            rightArr[j] = (T) array[midIndx + j + 1];
        }
        int i = 0;
        int j = 0;
        for (int k = begIndx; k <= endIndx; k++) {
            if (i == sizeOfLeft) {
                array[k] = (Comparable<? extends T>) rightArr[j++];
            } else if(j == sizeOfRight) {
                array[k] = (Comparable<? extends T>) leftArr[i++];
            } else if(((Integer) leftArr[i]).compareTo((Integer)rightArr[j]) <= 0) {
                array[k] = (Comparable<? extends T>) leftArr[i++];
            } else {
                array[k]=(Comparable<? extends T>) rightArr[j++];
            }
        }
    }

}

Если я дам ему массив из целых чисел из 5 вещей
5, 24, 79, 8, 3;

Тогда я должен получить 3,5,8,24,79 назад.

1 Ответ

1 голос
/ 26 мая 2019

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

Средний индекс должен быть на полпути между вашими begIndx и endIndx для этого вызова, вот чтовопросы.

...