Реализация сортировки слиянием с использованием массива вместо вектора

Question

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

void Merge(int ar[], int ar1[], int ar2[], int n1, int n2) {

    int p1 = 0;
    int p2 = 0;
    int p3 = 0;
    while (p1 < n1 && p2 < n2) {
        if (ar1[p1] < ar2[p2])
        {
            ar[p3]=ar1[p1];
            p3++;
            p1++;
        }
        else
        {
            ar[p3]=ar2[p2];
            p3++;
            p2++;
        }
    }

    while (p1 < n1)
    {
        ar[p3]=ar1[p1];
        p3++;
        p1++;
    }

    while (p2 < n2)
    {
        ar[p3]=ar2[p2];
        p3++;
        p2++;
    }
}

---

Я понял, как решить проблему, с которой столкнулся, с помощью приведенного ниже кода.

void Sortmerge(int array[],int n) {

    if (n <= 1) return;

    if (n % 2 == 0)
    {
        int arr1[n/2];
        int arr2[n/2];
        int k=0;
        int l=0;

        for (int i=0;i<n;i++)
        {
            if (i<(n/2))
            {
                arr1[k++]=array[i];
            }

            else
            {
                arr2[l++]=array[i];
            }
        }

        Sortmerge(arr1,n/2);
        Sortmerge(arr2,n/2);

        for (int i=0;i<n;i++)
        {
        array[i]=0;
        }

        Merge(array, arr1, arr2,n/2,n/2);
    }

    if (n%2!=0)
    {
        int arr1[(n-1)/2];
        int arr2[(n+1)/2];
        int k=0;
        int l=0;
        for (int i=0;i<n;i++)
        {
            if (i<((n-1)/2))
            {
                arr1[k++]=array[i];
            }

            else
            {
                arr2[l++]=array[i];
            }
        }

        Sortmerge(arr1,(n-1)/2);
        Sortmerge(arr2,(n+1)/2);

        for (int i=0;i<n;i++)
        {
            array[i]=0;
        }

        Merge(array, arr1, arr2,(n-1)/2,(n+1)/2 );
    }
}

Answer 1

Вы объявили два набора массивов. Два имени arr1 и два имени arr2. К ним добавлены некоторые данные, но затем они выходят за рамки и данные не используются. Это источник предупреждений.

Затем вы пытаетесь использовать arr1 и arr2 вне их областей действия - вне блоков if. Это источник ошибки. Эти массивы должны быть объявлены один раз, вероятно, в верхней части вашей функции (Sortmerge), прежде чем ваши n % 2 проверки.

Answer 2

Это кажется нормальным.

Вы объявляете два массива в операторе if . Область для вашей переменной только для этого утверждения. Заменить:

   if (n%2==0)
    {
        int arr1[n/2]; //<-------here
        int arr2[n/2]; //<-------here
        int k=0;
        int l=0;

от

   int arr1[n/2]; //<-------here
   int arr2[n/2]; //<-------here
   if (n%2==0)
    {
        int k=0;
        int l=0;

Answer 3

Когда вы пишете

if (n%2==0)
{
    int arr1[n/2]; //<-------here
    int arr2[n/2]; //<-------here
    ..........
}

arr1 и arr2 видны только коду в этой области (между {} с). Таким образом, у вас есть два разных набора arr1 и arr2, один для нечетного n и один для четного n, но ни один из них не виден вашим Sortmerge(...) вызовам.

Также вы можете заменить

if (n%2==0){
....
}

if (n%2!=0){
....
}

с

if (n%2==0){
....
}
else{
....
}