Язык C: Почему мой код получает бесконечный цикл и как использовать рекурсию для решения проблемы сортировки слиянием?

Question

Есть две проблемы, с которыми я сталкиваюсь в этом коде.

Первая проблема - это бесконечный цикл, возникший из 77 ~ 79.Когда я изменю эти тестовые данные и вместо этого использую метод слияния, я получу бесконечный цикл, и R1 изменится на 4198739. Но если я использую метод mergeSort, проблема не будет отображаться, как ожидалось.Как показано ниже:

  int M = 2;
  int R1 = 4;
  int arr[] = {3,9,8,20};
  merge(arr, L, M, R1);

Вторая проблема произошла от 57 до 69 строк. В этом методе mergeSort я попытался разделить массив unorder на подмассив.Однако на исходный массив это никак не влияет.

Вот мой код. Сортировка слиянием в C

void mergeSort(int arr[], int L, int R)
{
  if(L<R) { 
    return ;
  } else {
    int M = (L+R) / 2;
    mergeSort(arr, L, M);
    mergeSort(arr, M+1, R);
    merge(arr, L, M+1 ,R);
  }
}

Answer 1

вот код, связанный (другим) ответом:

#include <stdio.h>

    void merge(int arr[], int L, int M, int R) 
    {
        int LEFT_SIZE = M-L;
        int RIGHT_SIZE = R-M+1;
        int left[LEFT_SIZE];
        int right[RIGHT_SIZE];
        int i,j,k;

        for(i=L;i<M;i++)
        {
            left[i-L] = arr[i];
        }
        for(i=M;i<=R;i++)               //1. <= as R is also an index
        {
            right[i-M] = arr[i];
        }

        i=0;
        j=0;
        k=L;

        while(i<LEFT_SIZE && j<RIGHT_SIZE)
        {
            if(left[i] <= right[j])         //2. <= so that duplicates are not ignored
            {
                arr[k] = left[i];
                i++;
            } 
            else                    //3. use else to keep up the computing speed
            {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while(i<LEFT_SIZE)
        {
            arr[k] = left[i];
            i++;
            k++;
        }

        while(j<RIGHT_SIZE)
        {
            arr[k] = right[j];
            j++;
            k++;
        }

    }

    void mergeSort(int arr[], int L, int R)
    {
        if(L<R)                     //4. Better
        {
            int M = (L+R) / 2;
            mergeSort(arr, L, M);
            mergeSort(arr, M+1, R);
            merge(arr, L, M+1 ,R);
        }
    }

    int main() {

        int arr[] = {3,9,20,8,21,22};

        mergeSort(arr, 0, (sizeof(arr)/sizeof(int))-1); //5. Use size-1 as we are dealing with indices

        int i;
        printf("Final\n");
        for(i=0; i<(sizeof(arr)/sizeof(int)); i++) 
        {
            printf("i=%d, R=%d,arr[i]=%d\n",i,(sizeof(arr)/sizeof(int)), arr[i]);
        }
    }

, поэтому вставка кода в ответ не проблема

Answer 2

В mergeSort заменить это:

if(L<R)

На это:

if(L>=R)

Если присутствует L<Rтогда он всегда будет удовлетворен, потому что индекс L всегда будет меньше, чем R (при запуске).И это причина того, что вы получите бесконечный цикл.

Answer 3

В логике кода есть несколько ошибок.Я буду обращаться к нему правильным кодом.Сначала несколько указателей.

1. Логика работает с индексами массива, не путайте с ограничениями массива.
2. Я использовал оператор sizeof для получения верхнего предела массива.
3. Используйте if-else всякий раз, когда это возможно.

Полный код не может быть правильно добавлен здесь, поэтому - https://pastebin.com/ixickcQA

Основная ошибка была здесь:

for(i=M;i<=R;i++)               //1. <= as R is also an index
{
     right[i-M] = arr[i];
}