Как я могу реализовать алгоритм сортировки слиянием с 4-сторонним разделом без ошибки ArrayIndexOutOfBoundsException?

Question

Я пытаюсь реализовать алгоритм сортировки слиянием с 4-сторонним разделением в Java, проблема в том, что он генерирует ошибку ArrayIndexOutOfBoundsException в строке 85 алгоритма. Код выглядит следующим образом, я основан на двухстороннем алгоритме Merge Sort (традиционный алгоритм):

public static void mergeSort3WayRec(Integer[] gArray, int low, int high,
                                    Integer[] destArray) {
    if (high - low < 2) {
        return;
    }

    int mid1 = low + ((high - low) / 4);
    int mid2 = low + 2 * ((high - low) / 4) + 1;
    int mid3 = low + 3 * ((high - low) / 4) + 2;

    mergeSort3WayRec(destArray, low, mid1, gArray);
    mergeSort3WayRec(destArray, mid1, mid2, gArray);
    mergeSort3WayRec(destArray, mid2, mid3, gArray);
    mergeSort3WayRec(destArray, mid3, high, gArray);

    merge(destArray, low, mid1, mid2, mid3, high, gArray);
}

public static void merge(Integer[] gArray, int low, int mid1, int mid2, int mid3, int high,
                         Integer[] destArray) {
    int i = low, j = mid1, k = mid2, l = mid3, m = high;

    while ((i < mid1) && (j < mid2) && (k < mid3) && (l < high)) {
        if (gArray[i].compareTo(gArray[j]) < 0) {
            if (gArray[i].compareTo(gArray[k]) < 0) {
                if (gArray[i].compareTo(gArray[l]) < 0) {
                    destArray[m++] = gArray[i++];
                } else {
                    destArray[m++] = gArray[l++];
                }
            } else {
                destArray[m++] = gArray[k++];
            }
        } else {
            if (gArray[j].compareTo(gArray[k]) < 0) {
                if (gArray[j].compareTo(gArray[l]) < 0) {
                    destArray[m++] = gArray[j++];
                } else {
                    destArray[m++] = gArray[l++];
                }
            } else {
                if (gArray[k].compareTo(gArray[l]) < 0) {
                    destArray[m++] = gArray[k++];
                } else {
                    destArray[m++] = gArray[l++];
                }
            }
        }
    }

    while ((i < mid1) && (j < mid2)) {
        if (gArray[i].compareTo(gArray[j]) < 0) {
            destArray[m++] = gArray[i++];
        } else {
            destArray[m++] = gArray[j++];
        }
    }

    while ((j < mid2) && (k < mid3)) {
        if (gArray[j].compareTo(gArray[k]) < 0) {
            destArray[m++] = gArray[j++];
        } else {
            destArray[m++] = gArray[k++];
        }
    }

    while ((k < mid3) && (l < high)) {
        if (gArray[k].compareTo(gArray[l]) < 0) {
            destArray[m++] = gArray[k++];
        } else {
            destArray[m++] = gArray[l++];
        }
    }

    while ((i < mid1) && (k < mid3)) {
        if (gArray[i].compareTo(gArray[k]) < 0) {
            destArray[m++] = gArray[i++];
        } else {
            destArray[m++] = gArray[k++];
        }
    }

    while ((i < mid1) && (l < high)) {
        if (gArray[i].compareTo(gArray[l]) < 0) {
            destArray[m++] = gArray[i++];
        } else {
            destArray[m++] = gArray[l++];
        }
    }

    while ((j < mid2) && (l < high)) {
        if (gArray[j].compareTo(gArray[l]) < 0) {
            destArray[m++] = gArray[j++];
        } else {
            destArray[m++] = gArray[l++];
        }
    }

    while (i < mid1) {
        destArray[m++] = gArray[i++];
    }

    while (j < mid2) {
        destArray[m++] = gArray[j++];
    }

    while (k < mid3) {
        destArray[m++] = gArray[k++];
    }

    while (l < high) {
        destArray[m++] = gArray[l++];
    }
}

Следует отметить, что gArray является копией исходного массива, введенного в метод main, код этой части выглядит следующим образом:

public static void main(String args[]) {
    Integer[] data = new Integer[]{ 45, -2, -45, 78,
        30, -42, 10, 19, 73, 93, 80, 60, 2, 98, 85, 99 };
    mergeSort3Way(data);

    System.out.println("After 3 way merge sort: ");
    for (int i = 0; i < data.length; i++) {
        System.out.print(data[i] + " ");
    }
}

public static void mergeSort3Way(Integer[] gArray) {

    if (gArray == null) {
        return;
    }

    Integer[] fArray = new Integer[gArray.length];

    for (int i = 0; i < fArray.length; i++) {
        fArray[i] = gArray[i];
    }

    mergeSort3WayRec(fArray, 0, gArray.length, gArray);

    for (int i = 0; i < fArray.length; i++) {
        gArray[i] = fArray[i];
    }
}

У меня вопрос, как я могу решить эту ошибку? Кроме того, если есть дополнительная ошибка реализации, я уже новичок, делающий этот тип алгоритма. Спасибо.

Answer 1

Проблема выглядит так: ..., m = high, за которой следует destArray [m ++] = ...4 прогона, он должен опуститься до 3-х путей слияния.Чтобы избежать дублирования кода, вам нужно переместить индексы на низкий, средний1, средний2 и использовать средний или высокий значения для конца подмассива, начинающегося с середины 2.Когда трехстороннее слияние достигает конца одного из прогонов, оно должно быть спущено до двухстороннего слияния, а затем понижено до односторонней копии.

В сортировке слияния, если high-low <4,Вы можете просто выполнить сравнение с пузырьковой сортировкой и поменять местами на высокий - низкий == 3 или высокий - низкий == 2. </p>

Если предположить, что высокий-низкий <4 обрабатывается отдельно, то для более равномерной установки внутренних индексов(меньшие запуски слева): </p>

    int mid1 = low +(high+0-low)/4;
    int mid2 = mid1+(high+1-low)/4;
    int mid3 = mid2+(high+2-low)/4;

---

Пример кода для 4-сторонней сортировки слиянием сверху вниз с использованием пары взаимно рекурсивных функций, чтобы избежать обратного копирования, и «развернутой» логики слияния.Этот метод быстрее, чем выполнение множества условных выражений, но я думаю, что основное улучшение производительности связано с использованием сортировки вставок для небольших прогонов.Это тот случай, когда отсутствие «goto» в Java является проблемой, поскольку обходной путь, позволяющий избежать дублирования кода, заключается в установке и тестировании переменной «наименьший прогон» в процедуре слияния.

    static final int MINSIZE = 32;          // must be >= 3

    static void InsertionSort(Integer a[], int ll, int rr)
    {
    int i = ll+1;
    int j;
    Integer t;
        while(i < rr){
            t = a[i];
            j = i;
            while((j > ll) && a[j-1].compareTo(t)> 0){
                a[j] = a[j-1];
                j -= 1;}
        a[j] = t;
        i += 1;}
    }

    public static void MergeSort(Integer[] a)  // entry function
    {
        if(a.length < 2)                    // if size < 2 return
            return;
        Integer[] b = new Integer[a.length];
        MergeSortAtoA(a, b, 0, a.length);

    }

    static void MergeSortAtoA(Integer[] a, Integer[] b, int ll, int rr)
    {
        if(rr - ll <= MINSIZE){
            InsertionSort(a, ll, rr);
            return;}
        int m1 = ll+(rr+0-ll)/4;
        int m2 = m1+(rr+1-ll)/4;
        int m3 = m2+(rr+2-ll)/4;
        MergeSortAtoB(a, b, ll, m1);
        MergeSortAtoB(a, b, m1, m2);
        MergeSortAtoB(a, b, m2, m3);
        MergeSortAtoB(a, b, m3, rr);
        Merge(b, a, ll, m1, m2, m3, rr);
    }

    static void MergeSortAtoB(Integer[] a, Integer[] b, int ll, int rr)
    {
        if(rr - ll <= MINSIZE){
            System.arraycopy(a, ll, b, ll, rr-ll);
            InsertionSort(b, ll, rr);
            return;}
        int m1 = ll+(rr+0-ll)/4;
        int m2 = m1+(rr+1-ll)/4;
        int m3 = m2+(rr+2-ll)/4;
        MergeSortAtoA(a, b, ll, m1);
        MergeSortAtoA(a, b, m1, m2);
        MergeSortAtoA(a, b, m2, m3);
        MergeSortAtoA(a, b, m3, rr);
        Merge(a, b, ll, m1, m2, m3, rr);
    }

    static void Merge(Integer[] a, Integer[] b, int ll, int m1, int m2, int m3, int rr) {
        int bb = ll;                        // b[] index
        int a0 = ll;                        // a[] indexes
        int a1 = m1;
        int a2 = m2;
        int a3 = m3;
        while(true){                        // 4 way merge
            int sr;                         // smallest run
            if(a[a0].compareTo(a[a1]) <= 0){
                if(a[a2].compareTo(a[a3]) <= 0){
                    if(a[a0].compareTo(a[a2]) <= 0){
                        sr = 0;}
                    else{
                        sr = 2;}}
                else{
                    if(a[a0].compareTo(a[a3]) <= 0){
                        sr = 0;}
                    else{
                        sr = 3;}}}
            else{
                if(a[a2].compareTo(a[a3]) <= 0){
                    if(a[a1].compareTo(a[a2]) <= 0){
                        sr = 1;}
                    else{
                        sr = 2;}}
                else{
                    if(a[a1].compareTo(a[a3]) <= 0){
                        sr = 1;}
                    else{
                        sr = 3;}}}
            if(sr == 0){
                b[bb] = a[a0];
                bb++;
                a0++;
                if(a0 < m1)
                    continue;
                a0 = a1;
                a1 = a2;
                a2 = a3;
                m1 = m2;
                m2 = m3;
                m3 = rr;
                break;}
            if(sr == 1){
                b[bb] = a[a1];
                bb++;
                a1++;
                if(a1 < m2)
                    continue;
                a1 = a2;
                a2 = a3;
                m2 = m3;
                m3 = rr;
                break;}
            if(sr == 2){
                b[bb] = a[a2];
                bb++;
                a2++;
                if(a2 < m3)
                    continue;
                a2 = a3;
                m3 = rr;
                break;}
            else{  // sr == 3
                b[bb] = a[a3];
                bb++;
                a3++;
                if(a3 < rr)
                    continue;
                break;}
        }
        while(true){                        // 3 way merge
            int sr;                         // smallest run
            if(a[a0].compareTo(a[a1]) <= 0){
                if(a[a0].compareTo(a[a2]) <= 0){
                    sr = 0;}
                else{
                    sr = 2;}}
            else{
                if(a[a1].compareTo(a[a2]) <= 0){
                    sr = 1;}
                else{
                    sr = 2;}}
            if(sr == 0){
                b[bb] = a[a0];
                bb++;
                a0++;
                if(a0 < m1)
                    continue;
                a0 = a1;
                a1 = a2;
                m1 = m2;
                m2 = m3;
                break;}
            if(sr == 1){
                b[bb] = a[a1];
                bb++;
                a1++;
                if(a1 < m2)
                    continue;
                a1 = a2;
                m2 = m3;
                break;}
            else{ // sr == 2
                b[bb] = a[a2];
                bb++;
                a2++;
                if(a2 < m3)
                    continue;
                break;}
        }
        while(true){                        // 2 way merge
            if(a[a0].compareTo(a[a1]) <= 0){
                b[bb] = a[a0];
                bb++;
                a0++;
                if(a0 < m1)
                    continue;
                a0 = a1;
                m1 = m2;
                break;}
            else{
                b[bb] = a[a1];
                bb++;
                a1++;
                if(a1 < m2)
                    continue;
                break;}
        }
        System.arraycopy(a, a0, b, bb, m1-a0);  // 1 way copy
    }

---

Исправлена ​​версия кода chqrlie.

    public static void merge(Integer[] gArray, int low, int mid1, int mid2, int mid3, int high,
                             Integer[] destArray)
    {
        int i = low, j = mid1, k = mid2, l = mid3, m = low;

        while (m < high) {
            if (i < mid1 && (j >= mid2 || gArray[i].compareTo(gArray[j]) <= 0)) {
                if (k >= mid3 || gArray[i].compareTo(gArray[k]) <= 0) {
                    if (l >= high || gArray[i].compareTo(gArray[l]) <= 0) {
                        destArray[m++] = gArray[i++];
                    } else {
                        destArray[m++] = gArray[l++];
                    }
                } else {
                    if (k < mid3 && (l >= high || gArray[k].compareTo(gArray[l]) <= 0)) {
                        destArray[m++] = gArray[k++];
                    } else {
                        destArray[m++] = gArray[l++];
                    }
                }
            } else {
                if (j < mid2 && (k >= mid3 || gArray[j].compareTo(gArray[k]) < 0)) {
                    if (l >= high || gArray[j].compareTo(gArray[l]) < 0) {
                        destArray[m++] = gArray[j++];
                    } else {
                        destArray[m++] = gArray[l++];
                    }
                } else {
                    if (k < mid3 && (l >= high || gArray[k].compareTo(gArray[l]) < 0)) {
                        destArray[m++] = gArray[k++];
                    } else {
                        destArray[m++] = gArray[l++];
                    }
                }
            }
        }
    }

    public static void mergeSort4WayRec(Integer[] gArray, int low, int high,
                                        Integer[] tempArray) {
        if (high - low < 2) {
            return;
        }

        int mid1 = low  + (high + 0 - low) / 4;
        int mid2 = mid1 + (high + 1 - low) / 4;
        int mid3 = mid2 + (high + 2 - low) / 4;

        mergeSort4WayRec(tempArray, low,  mid1, gArray);
        mergeSort4WayRec(tempArray, mid1, mid2, gArray);
        mergeSort4WayRec(tempArray, mid2, mid3, gArray);
        mergeSort4WayRec(tempArray, mid3, high, gArray);

        merge(tempArray, low, mid1, mid2, mid3, high, gArray);
    }

    public static void mergeSort4Way(Integer[] gArray) {

        if (gArray != null) {
            Integer[] tempArray = new Integer[gArray.length];

            for (int i = 0; i < gArray.length; i++) {
                tempArray[i] = gArray[i];
            }
            mergeSort4WayRec(gArray, 0, gArray.length, tempArray);
        }
    }

    public static void main(String[] args) {
        Integer[] a = new Integer[1024*1024];
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        mergeSort4Way(a);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }

Answer 2

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

• Неправильное вычисление точек разбиения для небольших промежутков: low + 3 * ((high - low) / 4) + 2 больше high для high - low == 4. Вы должны просто использовать предложенную поправку rcgldr:

  int mid1 = low  + (high - low + 0) / 4;
  int mid2 = mid1 + (high - low + 1) / 4;
  int mid3 = mid2 + (high - low + 2) / 4;
  

• Выполнение четырехстороннего слияния для небольших массивов является излишним, особенно если размер меньше 4. Вы должны использовать вставную сортировку вместо high - low < 4 или, возможно, более высокое число, которое вы определите при тщательном тестировании производительности.

• имя mergeSort3WayRec вводит в заблуждение для реализации сортировки с четырьмя путями слияния:)

• m должно быть инициализировано low, а не high.

• в четырехсторонней фазе объединения отсутствует тест.

• когда один из массивов исчерпан, вы должны вернуться к трехсторонней фазе слияния, которая полностью отсутствует в вашем коде. Учитывая ваш подход, вам понадобятся 4 различных трехсторонних цикла слияния.

• тогда порядок выполнения оставшихся двухсторонних фаз слияния неверен, если вы хотите сохранить стабильность. На самом деле, вы должны проверить с <=, чтобы добиться стабильной сортировки.

• имя destArray в списке аргументов mergeSort3WayRec вводит в заблуждение, это временный массив, а не целевой массив.

• Циклы копирования в mergeSort3Way() неверны. mergeSort2WayRec вычисляет отсортированный на месте цикл копирования не требуется.

Вот более простой подход с комбинированными граничными тестами:

import java.io.*;
import java.lang.*;

public class main {

    public static void merge(Integer[] gArray, int low, int mid1, int mid2, int mid3,
                             int high, Integer[] destArray)
    {
        int i = low, j = mid1, k = mid2, l = mid3, m = low;

        while (m < high) {
            if (i < mid1 && (j >= mid2 || gArray[i].compareTo(gArray[j]) <= 0)) {
                if (k >= mid3 || gArray[i].compareTo(gArray[k]) <= 0) {
                    if (l >= high || gArray[i].compareTo(gArray[l]) <= 0) {
                        destArray[m++] = gArray[i++];
                    } else {
                        destArray[m++] = gArray[l++];
                    }
                } else {
                    if (k < mid3 && (l >= high || gArray[k].compareTo(gArray[l]) <= 0)) {
                        destArray[m++] = gArray[k++];
                    } else {
                        destArray[m++] = gArray[l++];
                    }
                }
            } else {
                if (j < mid2 && (k >= mid3 || gArray[j].compareTo(gArray[k]) <= 0)) {
                    if (l >= high || gArray[j].compareTo(gArray[l]) < 0) {
                        destArray[m++] = gArray[j++];
                    } else {
                        destArray[m++] = gArray[l++];
                    }
                } else {
                    if (k < mid3 && (l >= high || gArray[k].compareTo(gArray[l]) <= 0)) {
                        destArray[m++] = gArray[k++];
                    } else {
                        destArray[m++] = gArray[l++];
                    }
                }
            }
        }
        for (int i = low; i < high; i++) {
            gArray[i] = destArray[i];
        }
    }

    public static void mergeSort4WayRec(Integer[] gArray, int low, int high,
                                        Integer[] tempArray) {
        if (high - low < 2) {
            return;
        }

        int mid1 = low  + (high - low + 0) / 4;
        int mid2 = mid1 + (high - low + 1) / 4;
        int mid3 = mid2 + (high - low + 2) / 4;

        mergeSort4WayRec(gArray, low,  mid1, tempArray);
        mergeSort4WayRec(gArray, mid1, mid2, tempArray);
        mergeSort4WayRec(gArray, mid2, mid3, tempArray);
        mergeSort4WayRec(gArray, mid3, high, tempArray);

        merge(gArray, low, mid1, mid2, mid3, high, tempArray);
    }

    public static void mergeSort4Way(Integer[] gArray) {
        if (gArray != null) {
            Integer[] tempArray = new Integer[gArray.length];
            mergeSort4WayRec(gArray, 0, gArray.length, tempArray);
        }
    }

    public static void main(String[] args) {
        Integer arr[] = { 3, 2, 4, 1, 99, 30, 5, 3, 3, 2, 4, 1, 99, 30, 5, 3,
            3, 2, 4, 1, 99, 30, 5, 3 };

        long ns = System.nanoTime();
        mergeSort4Way(arr);
        ns = System.nanoTime() - ns;

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("\n" + arr.length + "elements sorted in " + ns + " ns");
    }
}

Answer 3

ArrayIndexOutOfBoundsException должно быть связано с добавлением 2 для вычисления mid3 для (high - low)/4 < 2. (Какова была идея этого? (Вызов функции mergeSort3WayRec() бесполезен, так как добавление 1 для вычисления mid2.))
Для вычисления splitP для P = 1, 2,…, n-1 с дисперсией 1 вместо n-1 ,
пусть count = high - low и просто установить splitP = low + (P * count) / n.