Рекурсивная сортировка слиянием в C без изменения исходного массива

Question

Я реализую сортировку слиянием в C. У меня есть функция слияния - merge(int array[], int start, int middle, int end) и функция слияния - mergeSort(int *array, unsigned int size).

Сортировка слиянием работает отлично, если отсортирована первая половина исходного массива и вторая половина исходного массива (например: 5,6,7,8,1,2,3,4). Это потому, что моя функция слияния получает исходный массив независимо от того, что, и она работает, когда ей дают 2 отсортированных массива (как и ожидалось). Моя проблема, когда они не. Каждый раз, когда я вызываю слияние, мой исходный массив не изменяется, хотя я и запрограммировал его для этого. Может кто-нибудь выяснить, где моя проблема? Код ниже.

Когда я запускаю этот код на входе {10,9,8,7,6,5,4,3,2,1}, он возвращает {5,4,3,2,1,0,10,9,8,7,6}.

void merge(int arr[], int l, int m, int r) {

    int size1 = m - l + 1;
    int size2 = r - m;

    int arr1[size1];
    int arr2[size2];

    int i;

    for ( i = 0; i < size1; i++ ) {
        arr1[i] = arr[l + i];
    }

    for ( i = 0; i < size2; i++ ) {
        arr2[i] = arr[m + i + 1];
    }

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

    while ( i < size1 && j < size2 ) {
        if ( arr1[i] < arr2[j] ) {
            arr[k] = arr1[i];
            i++;
            k++;
        } else {
            arr[k] = arr2[j];
            j++;
            k++;
        }
    }
    while ( i < size1 ) {
        arr[k] = arr1[i];
        i++;
        k++;
    }
    while ( j < size2 ) {
        arr[k] = arr2[j];
        j++;
        k++;
    }
}

void mergeSort(int *array, unsigned int size) {
    int start = 0;
    int middle = (size / 2) - 1;
    int end = size - 1;

    if ( size < 2 ) {
        return;
    }

    int m = ( size / 2 );

    int arr1[m];
    int arr2[size - m];

    int i;

    for ( i = 0; i < middle + 1; i++ ) {
        arr1[i] = array[i];
        printf("%d\n", arr1[i]);
    }

    for ( i = middle + 1; i < size; i++ ) {
        arr2[i - (middle + 1)] = array[i];
    }

    mergeSort(arr1, m);
    mergeSort(arr2, size - m);
    merge(array, start, middle, end);
}

Answer 1

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

• функция mergeSort разбивает массив на 2 локальных массива и рекурсивно вызывает себя для их сортировки, но фаза merge не принимает эти отсортированные массивы в качестве входных данных. Вместо этого вы должны напрямую использовать части массива аргументов.
• вычисления размера громоздки, со многими корректировками, которые могут создать проблемы для небольших значений size. Используйте простое соглашение: передайте end в качестве смещения первого элемента после конца массива. Таким образом, размер вычисляется просто путем вычитания start из end.
• , функция merge инициализирует k в 0 вместо l.

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

void merge(int arr[], int start, int m, int end) {
    int size1 = m - start;
    int size2 = end - m;
    int arr1[size1];
    int arr2[size2];
    int i, j, k;

    for (i = 0; i < size1; i++) {
        arr1[i] = arr[start + i];
    }
    for (i = 0; i < size2; i++) {
        arr2[i] = arr[m + i];
    }

    i = j = 0;
    k = start;

    while (i < size1 && j < size2) {
        if (arr1[i] < arr2[j]) {
            arr[k++] = arr1[i++];
        } else {
            arr[k++] = arr2[j++];
        }
    }
    while (i < size1) {
        arr[k++] = arr1[i++];
    }
    while (j < size2) {
        arr[k++] = arr2[j++];
    }
}

void mergeSort(int *array, unsigned int size) {
    if (size >= 2) {
        int m = size / 2;
        mergeSort(array, m);
        mergeSort(array + m, size - m);
        merge(array, 0, m, size);
}

Боб __ предложил упрощение, сохранив только первую половину массива до arr1 и исключив необходимость в arr2. Вот модифицированная версия, также удаляющая start, которая всегда 0, и некоторые другие упрощения:

void merge(int arr[], size_t m, size_t size) {
    int arr1[m];
    size_t i, j, k;

    for (i = j = k = 0; j < m; j++) {
        arr1[j] = arr[j];
    }

    while (i < m && j < size) {
        if (arr1[i] < arr[j]) {
            arr[k++] = arr1[i++];
        } else {
            arr[k++] = arr[j++];
        }
    }
    while (i < m) {
        arr[k++] = arr1[i++];
    }
}

void mergeSort(int *array, size_t size) {
    if (size >= 2) {
        size_t m = size / 2;
        mergeSort(array, m);
        mergeSort(array + m, size - m);
        merge(array, m, size);
}

Обратите внимание, однако, что выделение arr1 с автоматическим c хранилищем, то есть на стек может вызывать неопределенное поведение для больших массивов, обычно больше нескольких сотен тысяч элементов. Выделение временного массива из кучи позволяет избежать этой проблемы за счет дополнительных издержек и возможности сбоя при распределении.

Answer 2

В mergeSort, после выполнения mergeSort(arr1, m) и mergeSort(arr2, size - m), вы фактически ничего не делаете с arr1 и arr2.

. Для простого исправления я предлагаю не использовать переменные arr1 и arr2 и вызов mergeSort непосредственно для частей array, например:

void mergeSort(int* array, unsigned int size) {
    int start = 0;
    int middle = (size / 2);
    int end = size - 1;

    if ( size < 2 ) {
        return;
    }

    mergeSort(array, middle);
    mergeSort(array + middle, size - middle);
    merge(array, start, middle - 1, end);
}

Answer 3

Сортированное слияние для каждой рекурсии выполняется на локальном массиве, созданном в стеке, и не переносится на предыдущий вызов функции. Конечный результат всего рекурсивного вызова - не что иное, как слияние {10,9,8,7,6} и {5,4,3,2,1}.

. Вы можете найти отладочную проверку здесь .

Примечание: Выходные данные имеют различия в моем отладочном коде, поскольку вызывающая сторона mergeSort может иметь различную реализацию

Обновлен фрагмент кода следующим образом:

#include <stdio.h>
void merge(int arr[], int l, int m, int r) {

    int size1 = m - l;
    int size2 = r - m;

    int arr1[size1];
    int arr2[size2];

    int i;

    for ( i = 0; i < m; i++ ) {
        arr1[i] = arr[l + i];
    }

    for ( i = 0; i+m < r; i++ ) {
        arr2[i] = arr[m + i ];
    }

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

    while ( i < size1 && j < size2 ) {
        if ( arr1[i] < arr2[j] ) {
            arr[k++] = arr1[i++];
        } else {
            arr[k++] = arr2[j++];
            }
    }
    while ( i < size1 ) {
        arr[k++] = arr1[i++];
    }
    while ( j < size2 ) {
        arr[k++] = arr2[j++];
    }
}

void mergeSort(int* array, unsigned int size) {

    if ( size < 2 ) {
        return;
    }

    int start = 0;
    int middle = (size / 2);
    int end = size;

    mergeSort(array, middle);
    mergeSort(&array[middle], end-middle);
    merge(array, start, middle, end);
}


int main()
{
    int a[] = {10,9,8,7,6,5,4,3,2,1};
    const int size = sizeof(a)/sizeof(a[0]);
    mergeSort(a,size);
    for(int i=0;i<size;i++)
       printf("%d ", a[i]);
}

output: 1 2 3 4 5 6 7 8 9 10