C - Почему эта программа печатает два 0?

Question

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

MAIN

/* Test merge() and mergesort(). */

#include "mergesort.h"

int main(void) {
    int sz, key[] = {67, 55, 8, 0, 4, -5, 37, 7, 4, 2, 9, 1, -1};

    sz = sizeof(key) / sizeof(int);
    printf("Before mergesort:");
    wrt(key, sz);
    mergesort(key, sz);
    printf("After mergesort:");
    wrt(key, sz);
    return 0;
}

MERGE.C

/* Merge a[] of size m and b[] of size n into c[]. */
#include "mergesort.h"
void merge(int a[], int b[], int c[], int m, int n)
{
    int i = 0, j = 0, k = 0;

    while (i < m && j < n)
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    while (i < m)   /* pick up an remainder */
        c[k++] = a[i++];
    while (j < n)
        c[k++] = b[j++];
}

MERGESORT.C

/* Mergesort: Use merge() to sort an array of size n. */

#include "mergesort.h"
void mergesort(int key[], int n) // n is 0 to begin with
{
    int j,k,m, *w;
    int x,y;

    for (m = 1; m < n; m *= 2)      /*m is a power of 2*/
        if (n < m){
            printf("ERROR: Array size not a power of 2 - bye!\n");
            exit(1);
        }

    w = calloc(m, sizeof(int));     /* allocate workspace */
    assert(w != NULL);             /* check that calloc() worked */
    for (k = 1; k < n; k *= 2) {
        for (j = 0; j < n - k; j += 2 * k)
            /*
              Merge two subarrays of key[] into a subarray of w[].
            */
            merge(key + j, key + j + k, w + j, k, k); // todo: make the two k's not equal
        for (j = 0; j < n; ++j)
            key[j] = w[j];
    }


    free(w);
}

MERGESORT.H

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
void merge(int a[], int b[], int c[], int m, int n);
void mergesort(int key[], int n);
void wrt(int key[] , int sz);

WRT.C

#include "mergesort.h"

void wrt(int key[], int sz)
{
    int i;

    for (i = 0; i < sz; ++i)
        printf("%4d%s", key[i], ((i < sz - 1) ? "" : "\n"));
}

Когда это распечатано, есть два нуля. Как это происходит? Я думаю, что секрет этого кроется в mergesort.c со значением k. Как вы можете видеть в нижней части, я прокомментировал в «todo: сделать два k не равными», это упрощенное решение, которое предложил мне мой учитель. Я также вставил в х и у, которые будут отдельными значениями к. Но я не понимаю, как я могу разделить это одно значение на два?

Answer 1

Проблема в этой части кода функции mergesort():

    for (m = 1; m < n; m *= 2)      /*m is a power of 2*/
    if (n < m){
        printf("ERROR: Array size not a power of 2 - bye!\n");
        exit(1);
    }

Предполагается, что проверяется, имеет ли размер массива, подлежащий сортировке, размер в степени 2, а размер передаваемого массива 13 (а не 2) ):

int sz, key[] = {67, 55, 8, 0, 4, -5, 37, 7, 4, 2, 9, 1, -1};

он должен выдать ошибку и завершиться, но поскольку проверка power of 2 неверна, он продолжается и ваш код сортировки слиянием не способен сортировать массив неравномерного размера . Следовательно, вы получаете неправильный вывод для массива неравного размера.

В цикле for

for (m = 1; m < n; m *= 2) 
            ^^^^^

цикл будет повторяться до m < n и в теле цикла if условие, которое вы проверяете

if (n < m){ ....

, что никогда не произойдет, потому что как только m > n цикл завершится.

Вместо проверки мощности 2, я думаю, вы хотите проверить, равен ли размер массива even или нет. Чтобы проверить, является ли размер даже или нет, вы можете просто сделать:

   if (n & 1)
   {
       printf("ERROR: Array size not a multiple of 2 - bye!\n");
       exit(1);
   }

Для сортировки массива с использованием сортировки слиянием необязательно, чтобы размер массива составлял , даже . Вы можете использовать сортировку слиянием для сортировки массива размером odd . Отметьте этот ответ .