Нужно ли передавать индексы в качестве аргументов при выполнении сортировки слиянием? - PullRequest
Новая
       22

Нужно ли передавать индексы в качестве аргументов при выполнении сортировки слиянием?

0 голосов
/ 08 июля 2019

Я вижу, что многие реализации сортировки слиянием, которые я вижу в сети, такие как https://www.geeksforgeeks.org/merge-sort/, передают аргументы l, m и r, чтобы знать, где начинаются и заканчиваются подмассивы.Мне было интересно, если бы время выполнения и сложность пространства не изменились, если бы мы вместо этого сделали копии вложенных массивов и передали их. Пример предлагаемого кода выглядит следующим образом: 

class Solution {

    //mergeSort implementation
    public int[] sortArray(int[] nums) {

        if (nums.length == 1) {
            return nums;
        }

        int arrayLength = nums.length;

        // make copies instead of passing indices
        int[] left = Arrays.copyOfRange(nums, 0, arrayLength/2);
        int[] right = Arrays.copyOfRange(nums, arrayLength/2, arrayLength);

        left = sortArray(left);
        right = sortArray(right);

        return merge(left, right);

    }

    public int[] merge(int[] left,int[] right) {

        int[] merged = new int[left.length + right.length];

        int mergedCounter = 0;
        int i = 0; //leftCounter
        int j = 0; //rightCounter
        while (mergedCounter != left.length + right.length) {
            if (i == left.length) {
                merged[mergedCounter] = right[j];
                mergedCounter++;
                j++;
            } else if (j == right.length) {
                merged[mergedCounter] = left[i];
                mergedCounter++;
                i++;
            } else {
                if (left[i] <= right[j]) {
                    merged[mergedCounter] = left[i];
                    mergedCounter++;
                    i++;
                } else {
                    merged[mergedCounter] = right[j];
                    mergedCounter++;
                    j++;
                }
            }
        }

        return merged;

    }

}

Я считаю, что сложность выполнения неувеличено, потому что создание копии занимает то же время выполнения, что и инициализация нового массива n-длины через new int [n].Эта часть проблемы также включает подфункцию слияния O (n), так что это не имеет значения.

Я также считаю, что сложность пространства остается неизменной.В то время как мы создаем два временных подмассива в рекурсивном вызове, на шаге слияния будет создан тот же объем пространства, который указан в онлайн-решениях с использованием указателей на l, m и r.

Допустим ли мой мыслительный процессили я что-то упустил?

1 Ответ

2 голосов
/ 08 июля 2019

Любые дополнительные операции копирования увеличат время выполнения. Создание копий подмассивов увеличит требования к пространству на постоянную, но, поскольку «сложность» игнорирует константы и / или члены более низкого порядка, «сложность» пространства останется прежней.

В большинстве библиотек используется некоторая разновидность сортировки слиянием снизу вверх, где индексы (или указатели) обновляются на лету, а не передаются через рекурсию и обычно хранятся в регистрах на основе оптимизации компилятора. Сортировка сверху вниз в основном используется в качестве учебного упражнения.

Операции копирования могут быть сведены к минимуму путем изменения направления слияния на основе прохода слияния для сортировки слиянием снизу вверх или на основе уровня рекурсии для сортировки слиянием сверху вниз.

В C / C ++ альтернативой для передачи массива и индекса является передача указателя или итератора, что уменьшает количество параметров, необходимых для каждого вызова, на 1 параметр.

...