Проблема с алгоритмом сортировки слиянием - PullRequest
Новая
       32

Проблема с алгоритмом сортировки слиянием

2 голосов
/ 25 мая 2019

Алгоритм MergeSorting не работает.Продолжайте получать IndexOutOFBoundsError.Я полагаю, что проблема может быть в том, что нет стража.Мне нужно создать цикл, когда leftarray и rightarray копирует себя в k, в одном из массивов заканчиваются номера, что вызывает ошибку.Мне нужна помощь в создании этого стража. 

private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {
    if (items.length > 1) {
        int midIndx = items.length / 2;
        @SuppressWarnings("unchecked")
        T[] left = (T[]) new Object[midIndx];
        @SuppressWarnings("unchecked")
        T[] right = (T[]) new Object[items.length - midIndx];

        for (int i = 0; i < midIndx; i++) {
            left[i] = (T) items[i];
        }
        for (int i = midIndx; i < items.length; i++) {
            right[i] = (T) items[i];
        }

        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;

    // changed to less than or equal to rather than "less than"
    // this is because this is a zero based index system
    // and because endeIndex is not a length but an index,
    // you need to populate it.
    for (int k = begIndx; k <= endIndx; k++) {
        // use comparable here
        if (((Integer) leftArr[i]).compareTo((Integer) rightArr[j]) <= 0) {
            array[k] = (Comparable<? extends T>) leftArr[i];
            i = i + 1;
        } else if (((Integer) leftArr[i]).compareTo((Integer) rightArr[j]) >= 0) {
            /// just replaces it so don't use comparable
            array[k] = (Comparable<? extends T>) rightArr[j];
            j = j + 1;
        } else if ((Integer) leftArr[sizeOfLeft] == null) {
            array[k] =  (Comparable<? extends T>) rightArr[j];
            j = j + 1;
        } else if ((Integer) rightArr[sizeOfRight] == null) {
            array[k] = (Comparable<? extends T>) leftArr[i];
            i = i + 1;
        }
    }
}

Я создал целочисленный массив arr = new Integer[5].Поэтому эти 5 номеров должны быть отсортированы.

1 Ответ

2 голосов
/ 26 мая 2019

В вашем коде несколько проблем:

  • Неясно, включен или исключен индекс endIndx.Код будет намного проще, если исключить endIndx, а первоначальный вызов для сортировки массива будет просто: mergesort(arr, 0, arr.length);

  • первоначальный тест в mergesort неверен: вместо этогопри проверке длины массива вы должны проверить, имеет ли срез более 1 элемента: 

    if (endIndx - begIndx > 1)

  • массивы left и right не используются в mergesort.

  • выделение дополнительного элемента в массивах left и right в merge не требуется, намного проще сравнивать значения индекса массива с длинами подмассивов.Этот подход sentinel сбивает с толку и не должен использоваться.

Вот упрощенная версия: 

private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {
    if (endIndx - begIndx > 1) {
        int midIndx = items.length / 2;
        mergeSort(items, begIndx, midIndx);
        mergeSort(items, midIndx, 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;
    int sizeOfRight = endIndx - midIndx;

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

    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];
    }

    int i = 0;
    int j = 0;
    int k = begIndx;

    while (i < sizeOfLeft && j < sizeOfRight) {
        /// use comparable to compare actual values
        if ((Integer)leftArr[i]).compareTo((Integer)rightArr[j]) <= 0) {
            array[k] = (Comparable<? extends T>)leftArr[i];
            i++;
            k++;
        } else {
            array[k] = (Comparable<? extends T>)rightArr[j];
            j++;
            k++;
        }
    }
    while (i < sizeOfLeft) {
        array[k] = (Comparable<? extends T>)leftArr[i];
        i++;
        k++;
    }
    while (j < sizeOfRight) {
        array[k] = (Comparable<? extends T>)rightArr[j];
        j++;
        k++;
    }
}
...