Есть ли разница в сложности времени / пространства между алгоритмом рекурсивной и нерекурсивной сортировки слиянием?

Question

Я реализовал алгоритм сортировки слиянием, используя подход «разделяй и властвуй», когда массив разбивается на два подмассива.

В моем коде я повторно использовал алгоритм сортировки вставками для сортировки подмассивов в сортировке слиянием. Это правильный подход, или мне нужно использовать другой подход сортировки для сортировки подмассивов в сортировке слиянием?

Что касается понимания алгоритма сортировки слиянием, все понятно, но когда дело доходит до реализации слияния sort, как получается разделить массив на массивы n-sub без использования рекурсивной стратегии.

- это рекурсивный или нерекурсивный эффективный способ реализации сортировки слиянием?

Ниже приведен мой фрагмент кода в github: https://github.com/vamsikankipati/algorithms-in-java/blob/master/src/com/algorithms/sort/MergeSort.java

Я понял с точки зрения реализации, что мой код неверен, так как я разделил массив только на два вложенных массива вместо n-sub массивов.

Любая помощь, необходимая для четкого понимания сортировки слиянием с точки зрения реализации алгоритма.

Вот код:

package com.algorithms.sort;

public class MergeSort {

    public static int[] increasing(int[] arr) {
        int[] result = new int[arr.length];
        int q = arr.length / 2;
        System.out.println("q: " + q);
        int[] left = new int[q];
        int[] right = new int[q];
        for (int i = 0; i < q; i++) {
            left[i] = arr[i];
        }
        int k = 0;
        for (int j = q; j < arr.length; j++) {
            right[k] = arr[j];
            k += 1;
        }
        left = InsertionSort.increasing(left);
        right = InsertionSort.increasing(right);

        // Printing
        for (int e : left) {
            System.out.print(e);
        }
        System.out.println("\n");
        for (int e : right) {
            System.out.print(e);
        }
        System.out.println("\n");

        int i = 0;
        int j = 0;
        int s = 0;
        while ((i < left.length) && (j < right.length)) {
            if (left[i] <= right[j]) {
                result[s] = left[i];
                i++;
            } else {
                result[s] = right[j];
                j++;
            }
            s++;
        }
        while (i < left.length) {
            result[s] = left[i];
            i++;
            s++;
        }
        while (j < right.length) {
            result[s] = right[j];
            j++;
            s++;
        }
        return result;
    }

    /**
     * Main method to test an example integer array
     */
    public static void main(String[] args) {
        int[] ar = { 18, 12, 11, 6, 55, 100 };
        int[] res = increasing(ar);
        for (int a : res) {
            System.out.print(a + " ");
        }
    }
}

Answer 1

Важнее, чем оптимизация, вы должны сначала достичь правильности. В методе increasing stati c есть ошибка: если размер аргумента массива не является четным, подмассив right имеет неправильный размер: int[] right = new int[q]; должно быть

int[] right = new int[arr.length - q];

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

Что касается оптимизации, вы должны отступать до InsertionSort() только тогда, когда размер подмассива ниже порога, где-то между 16 и 128 элементами , Тщательный бенчмаркинг с различными пороговыми значениями и различными распределениями поможет определить хороший порог для вашей системы.

В настоящее время ваша функция имеет временную сложность O (N ² ). ) , потому что это относится к InsertionSort для всех, кроме последней фазы слияния. Чтобы уменьшить сложность до O (N.log (N)) , вы должны выполнять возврат на подмассивах до тех пор, пока их размер не станет ниже фиксированного порога.

Вот измененная версия:

package com.algorithms.sort;

public class MergeSort {

    public static int threshold = 32;

    public static int[] increasing(int[] arr) {
        if (arr.length <= threshold)
            return InsertionSort.increasing(arr);

        int len1 = arr.length / 2;
        int[] left = new int[len1];
        for (int i = 0; i < len1; i++) {
            left[i] = arr[i];
        }
        int len2 = arr.length - len1;
        int[] right = new int[len2];
        for (int i = 0; i < len2; i++) {
            right[i] = arr[i + len1];
        }
        left = increasing(left);
        right = increasing(right);

        int[] result = new int[len1 + len2];
        int i = 0;
        int j = 0;
        int s = 0;
        while (i < len1 && j < len2) {
            if (left[i] <= right[j]) {
                result[s] = left[i];
                i++;
            } else {
                result[s] = right[j];
                j++;
            }
            s++;
        }
        while (i < len1) {
            result[s] = left[i];
            i++;
            s++;
        }
        while (j < len2) {
            result[s] = right[j];
            j++;
            s++;
        }
        return result;
    }

    /**
     * Main method to test an example integer array
     */
    public static void main(String[] args) {
        int[] ar = { 18, 12, 11, 6, 55, 100 };
        int[] res = increasing(ar);
        for (int a : res) {
            System.out.print(a + " ");
        }
    }
}

Answer 2

Обе сложности времени O (n log n).

Что касается сложности пространства, реализация может варьироваться в зависимости от выбора структуры данных. в рекурсивном, если вы выбираете массив: сложность пространства: N log N, если вы выбираете связанный список: сложность пространства равна O (1), в итеративном: если вы выбираете массив: сложность пространства: N (в зависимости от вашей реализации это O (N log) N) поскольку вы создаете новый подмассив в каждом состоянии деления, чтобы уменьшить его до O (n), вы должны использовать один дополнительный массив как размер исходного и индексов), если вы выбираете связанный список: сложность пространства равна O (1)

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

Источник