Почему мой базовый случай (ошибочно) запускается немедленно? - PullRequest
Новая
       25

Почему мой базовый случай (ошибочно) запускается немедленно?

0 голосов
/ 25 января 2020

Я пытаюсь реализовать алгоритм сортировки слиянием в C. В рекурсивной функции разбиения массива мой базовый случай происходит бесконечно, несмотря на оператор return, и функция слияния никогда не вызывается. Вот мой код: 

#include <stdio.h>

const int MAX = 1000;

int getArray(int unsorted[MAX], int upperBound)
{
    int i;
    for(i = 0; i <= upperBound; ++i)
    {
        printf("Now enter integer number %d: ", i + 1);
        scanf("%d", &unsorted[i]);
        while((getchar()) != '\n');
    }   
    printf("\n");
    return 0;
}

int merge(int unsorted[MAX], int sorted[1000], int lowerLeft, int lowerRight)
{
    if(lowerLeft == lowerRight)
        return 0;
    int j = lowerRight;
    for(int i = lowerLeft; i < lowerRight; ++i)
    {
        if(unsorted[i] <= unsorted[j])
        {
            sorted[i] = unsorted[i];
            ++j;
        }
        else
        {
            sorted[i] = unsorted[j];
            ++j;
        }
    }
    return 1;
}

int split(int unsorted[MAX], int sorted[1000], int lowerBound, int upperBound)
{
    printf("%d is the lBound and %d is the uBound\n", lowerBound, upperBound);
    if(lowerBound == upperBound)
    {
        printf("\nBase case triggered.");
        getchar();
        return 0;
    }
    int middle = upperBound/2;
    split(unsorted, sorted, 0, middle);
    split(unsorted, sorted, middle + 1, upperBound);    
    merge(unsorted, sorted, lowerBound, middle);
    return 1;
}

int main()
{
    int unsorted[MAX];
    int sorted[MAX];
    int lowerBound = 0;
    int upperBound;

    printf("First enter the number of integers you wish to sort: ");
    scanf("%d", &upperBound);
    while((getchar()) != '\n');
    printf("\n");
    upperBound = upperBound - 1;
    getArray(unsorted, upperBound);
    split(unsorted, sorted, lowerBound, upperBound);
    printf("\n");
    for(int c = 0; c < upperBound; ++c)
    {
        printf("%d, ", sorted[c]);
    }

    return 0;
}

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

1 Ответ

1 голос
/ 25 января 2020

Ваш базовый случай запускается, потому что именно так работают рекурсивные алгоритмы. Вы продолжаете вызывать split() снова и снова с нижним и нижним промежутком между lowerBound и upperBound, поэтому в конечном итоге ваш базовый случай срабатывает. И это должно быть хорошо, поскольку запуск базового варианта позволяет вам знать, что ваши входные «массивы» (синглтоны) отсортированы и могут быть объединены.

Причина, по которой он запускается «немедленно», заключается в том, что он должен : split () вызывается непрерывно до тех пор, пока не будет достигнут базовый случай, поэтому первый оператор print, который вы увидите, - это базовый случай.

...