Неправильный результат программы Mergesort

Question

Я пытаюсь реализовать программу Mergesort, которая работает с массивом n элементов следующим образом. В этой программе вместо создания двух отдельных массивов L и R, которые содержат все номера массива a слева и справа, я попытался сократить его до одного массива, который имеет эквивалентное количество элементов как массив a

#include <stdio.h>

#define MAX 1000

void merge(int a[], int l, int m, int r) {
    int i, j, k = 0; 
    int b[r + 1];
    for (i = m; i >= 0; i--)
        b[i] = a[i]; 
    for (j = m + 1; j < r; j++) 
        b[r + m - j] = a[j]; 
    while (i <= m && j > m) { 
        if (b[i] <= b[j]) { 
            a[k] = b[i];
            i++; 
        } else { 
            a[k] = b[j];
            j--; 
        } 
        k++; 
    }
    while (i <= m) { 
        a[k] = b[i];
        i++;
        k++; 
    } 
    while (j > m) { 
        a[k] = b[j];
        j--;
        k++; 
    } 
} 

void mergesort(int a[], int l, int r) {
    int i, j, k, mid;
    int b[r + 1];
    if (r > l) {
        mid = (l + r) / 2;
        mergesort(a, l, mid);
        mergesort(a, mid + 1, r);
        merge(a, l, mid, r);
    }
}

int main() {
    int n;
    int i = 0;
    int a[MAX];
    printf("Enter the number of element you want to create: ");
    scanf("%d", &n);
    while (i < n) {
        printf("Enter your number %d: ", i);
        scanf("%d", &a[i]);
        i++;
    }
    mergesort(a, 0, n);
    i = 0;
    while (i < n) {
        printf("%d ", a[i]);
        i++;
    }
    return 0;
}

Когда я запускаю эту программу, она дала мне неправильный результат, и я не знаю, где я ошибаюсь.

Answer 1

Этот код показывает, как я инструментировал алгоритм. Первоначально это было сделано с безусловными вызовами printf() и dump_array() - когда он работал, они были преобразованы в макросы, чтобы код можно было скомпилировать с помощью -DDEBUG для получения подробной трассировки или без, чтобы просто получить результат.

Я не удалил код подсказки, но мои собственные программы этого не сделали. Возможно, я бы также подсчитал, сколько значений было введено программой (используя динамическое выделение памяти c, чтобы освободить место для данных), и просто считывал данные, пока они не достигнут EOF. Для тестирования я использовал три набора случайно сгенерированных чисел, сохраненных в файлах, чтобы тесты можно было повторять.

Я не пытался исправить исходный код merge() - я просто переписал его. Мои комментарии к вопросу обрисовывают в общих чертах некоторые проблемы с оригинальным кодом. Я вполне уверен, что код в вопросе не уделяет достаточного внимания, какие диапазоны чисел действительны. Этот код комментирует, что диапазоны до mergesort() и merge() включают конечные индексы (следовательно, main() вызывает mergesort(a, 0, n - 1), а не mergesort(a, 0, n), как, например, в вопросе).

Это код слияния сначала копирует данные в массив b, а затем сливается из b обратно в a (более или менее как код в вопросе) - было бы целесообразно объединить в b, а затем скопировать из b до a снова.

#include <assert.h>
#include <stdio.h>
#define MAX 1000

#ifdef DEBUG
#define TRACE(...)          printf(__VA_ARGS__)
#define DUMP(t, a, l, r)    dump_array(t, a, l, r)
#else
#define TRACE(...)          ((void)0)
#define DUMP(t, a, l, r)    ((void)0)
#endif

/* Dump elements in range l <= i <= r */
static void dump_array(const char *tag, int a[], int l, int r)
{
    assert(tag != 0 && a != 0 && l >= 0 && l <= r);
    printf("%s[%d..%d]:", tag, l, r);
    for (int i = l; i <= r; i++)
        printf(" %d", a[i]);
    putchar('\n');
}

/* Merge elements in ranges l <= i <= m and m+1 <= j <= r */
static void merge(int a[], int l, int m, int r)
{
    assert(a != 0 && l >= 0 && l <= m && m <= r);
    TRACE("-->> %s(): %d..%d..%d\n", __func__, l, m, r);
    int b[r + 1];
    for (int i = l; i <= r; i++)
        b[i] = a[i];
    DUMP("b", b, l, r);
    int k = l;
    int i = l;
    int j = m + 1;
    while (i <= m && j <= r)
    {
        if (b[i] <= b[j])
            a[k++] = b[i++];
        else
            a[k++] = b[j++];
    }
    while (i <= m)
        a[k++] = b[i++];
    while (j <= r)
        a[k++] = b[j++];
    DUMP("a", a, l, r);
    TRACE("<<-- %s(): %d..%d..%d\n", __func__, l, m, r);
}

/* Sort elements in range l <= i <= r */
static void mergesort(int a[], int l, int r)
{
    assert(a != 0 && l >= 0 && l <= r);
    if (r > l)
    {
        TRACE("-->> %s(): %d..%d\n", __func__, l, r);
        DUMP("a", a, l, r);
        int mid = (l + r) / 2;
        mergesort(a, l, mid);
        DUMP("a", a, l, mid);
        mergesort(a, mid + 1, r);
        DUMP("a", a, mid+1, r);
        merge(a, l, mid, r);
        DUMP("a", a, l, r);
        TRACE("<<-- %s(): %d..%d\n", __func__, l, r);
    }
}

int main(void)
{
    int n;
    int a[MAX];
    printf("Enter the number of elements you want to create: ");
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX)
    {
        fprintf(stderr, "read error\n");
        return 1;
    }
    for (int i = 0; i < n; i++)
    {
        printf("Enter your number %d: ", i);
        if (scanf("%d", &a[i]) != 1)
        {
            fprintf(stderr, "read error\n");
            return 1;
        }
    }
    putchar('\n');

    dump_array("Unsorted", a, 0, n - 1);
    mergesort(a, 0, n - 1);
    dump_array("Sorted", a, 0, n - 1);

    return 0;
}

Пример выполнения (-DDEBUG; набор данных из 5 элементов - которые печатаются, конечно, для проверки):

Enter the number of elements you want to create: Enter your number 0: Enter your number 1: Enter your number 2: Enter your number 3: Enter your number 4: 
Unsorted[0..4]: 17 74 63 62 26
-->> mergesort(): 0..4
a[0..4]: 17 74 63 62 26
-->> mergesort(): 0..2
a[0..2]: 17 74 63
-->> mergesort(): 0..1
a[0..1]: 17 74
a[0..0]: 17
a[1..1]: 74
-->> merge(): 0..0..1
b[0..1]: 17 74
a[0..1]: 17 74
<<-- merge(): 0..0..1
a[0..1]: 17 74
<<-- mergesort(): 0..1
a[0..1]: 17 74
a[2..2]: 63
-->> merge(): 0..1..2
b[0..2]: 17 74 63
a[0..2]: 17 63 74
<<-- merge(): 0..1..2
a[0..2]: 17 63 74
<<-- mergesort(): 0..2
a[0..2]: 17 63 74
-->> mergesort(): 3..4
a[3..4]: 62 26
a[3..3]: 62
a[4..4]: 26
-->> merge(): 3..3..4
b[3..4]: 62 26
a[3..4]: 26 62
<<-- merge(): 3..3..4
a[3..4]: 26 62
<<-- mergesort(): 3..4
a[3..4]: 26 62
-->> merge(): 0..2..4
b[0..4]: 17 63 74 26 62
a[0..4]: 17 26 62 63 74
<<-- merge(): 0..2..4
a[0..4]: 17 26 62 63 74
<<-- mergesort(): 0..4
Sorted[0..4]: 17 26 62 63 74

Пробный прогон (-UDEBUG с 12 элементами - набор из 5 элементов использует первые 5 чисел из этого набора):

Enter the number of elements you want to create: Enter your number 0: Enter your number 1: Enter your number 2: Enter your number 3: Enter your number 4: Enter your number 5: Enter your number 6: Enter your number 7: Enter your number 8: Enter your number 9: Enter your number 10: Enter your number 11: 
Unsorted[0..11]: 17 74 63 62 26 16 15 86 80 17 35 69
Sorted[0..11]: 15 16 17 17 26 35 62 63 69 74 80 86

Пробный прогон (-UDEBUG с 30 элементами - отдельный набор случайные числа в целом):

Enter the number of elements you want to create: Enter your number 0: Enter your number 1: Enter your number 2: Enter your number 3: Enter your number 4: Enter your number 5: Enter your number 6: Enter your number 7: Enter your number 8: Enter your number 9: Enter your number 10: Enter your number 11: Enter your number 12: Enter your number 13: Enter your number 14: Enter your number 15: Enter your number 16: Enter your number 17: Enter your number 18: Enter your number 19: Enter your number 20: Enter your number 21: Enter your number 22: Enter your number 23: Enter your number 24: Enter your number 25: Enter your number 26: Enter your number 27: Enter your number 28: Enter your number 29: 
Unsorted[0..29]: 80 76 86 10 46 99 12 55 76 34 86 23 76 83 13 21 93 50 19 53 86 92 81 35 90 53 65 67 79 20
Sorted[0..29]: 10 12 13 19 20 21 23 34 35 46 50 53 53 55 65 67 76 76 76 79 80 81 83 86 86 86 90 92 93 99

Я проверил набор из 30 элементов - взял список несортированных чисел, отсортировал их по sort -n и сравнил этот список с отсортированным выводом. Результат был идентичным, что означает, что свойства сортировки «порядок» и «сохранение» были действительны. Я оценил результаты для наборов 5 и 12 значений данных.

Answer 2

Предостережение: Для скорости / усталости я позаимствовал merge по ссылке, упомянутой в моих главных комментариях, и немного ее почистил.

И я переименовал переменные чтобы более точно соответствовать вашему.

Он соответствует функциям слияния, которые я написал ранее.

Одно отличие состоит в том, что он выполняет операцию копирования с b до a в конце, а точнее чем выполнять операцию копирования с a до b в начале.

И, как я упоминал выше, он не пересекает массивы в отрицательном направлении [такого подхода я раньше не видел] .

Кроме того, временный массив b всегда индексирует, начиная с 0, независимо от значений l, m или r. Это немного упрощает вещи.

Для отладки я немного изменил main, чтобы он выполнял автоматический c тест в худшем случае, и в конце сделал проверку сортировки вместе с некоторой отладкой printf

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

void
merge(int a[], int l, int m, int r)
{
    static int b[MAX];
    int i;
    int j;
    int k;

    printf("merge: ENTER l=%d m=%d r=%d\n",l,m,r);

    k = 0;
    i = l;
    j = m + 1;

    for (;  (i <= m) && (j <= r);  ++k) {
        if (a[i] <= a[j])
            b[k] = a[i++];
        else
            b[k] = a[j++];
    }

    for (;  i <= m;  ++i, ++k)
        b[k] = a[i];

    for (;  j <= r;  ++j, ++k)
        b[k] = a[j];

    k = 0;
    for (i = l;  i <= r;  ++i, ++k)
        a[i] = b[k];

    printf("merge: EXIT\n");
}

void
merge_original(int a[], int l, int m, int r)
{
    int i,
     j,
     k = 0;

    printf("merge: ENTER l=%d m=%d r=%d\n",l,m,r);

#if 1
    int b[r + 1];
    for (i = m; i >= 0; i--)
        b[i] = a[i];
#endif

    for (j = m + 1; j < r; j++)
        b[r + m - j] = a[j];

    while (i <= m && j > m) {
        if (b[i] <= b[j]) {
            a[k] = b[i];
            i++;
        }
        else {
            a[k] = b[j];
            j--;
        }
        k++;
    }

    while (i <= m) {
        a[k] = b[i];
        i++;
        k++;
    }

    while (j > m) {
        a[k] = b[j];
        j--;
        k++;
    }

    printf("merge: EXIT\n");
}

void
mergesort(int a[], int l, int r)
{
    int i,
     j,
     k,
     mid;
    int b[r + 1];

    if (r > l) {
        mid = (l + r) / 2;
        mergesort(a, l, mid);
        mergesort(a, mid + 1, r);
        merge(a, l, mid, r);
    }
}

int
main(void)
{
    int n;
    int i;
    int a[MAX];

    printf("Enter the number of element you want to create: ");
    scanf("%d", &n);

    for (i = 0;  i < n;   ++i) {
#if 0
        printf("Enter your number %d: ", i);
        scanf("%d", &a[i]);
#else
        a[i] = n - i;
#endif
        printf("SET %d: %d\n", i, a[i]);
    }

    mergesort(a, 0, n);

    int oval = -1;
    int cval;
    for (i = 0;  i < n;   ++i, oval = cval) {
        cval = a[i];

        printf("CMP %d: %d\n", i, cval);

        if (cval < oval) {
            printf("fault\n");
            exit(1);
        }
    }

    return 0;
}

---

ОБНОВЛЕНИЕ:

У меня вопрос, что в функции merge, что функция третьего for l oop здесь?

Обратите внимание, что [в и ваш код и обновленный код] b - это временный массив.

Есть всего четыре цикла:

(1) «объединение» l oop [которое принимает наименьшее из любого подмассива, в то время как у у обоих подмассивов все еще есть оставшиеся элементы]:

for (;  (i <= m) && (j <= r);  ++k)

(2) Второй l oop копирует любые элементы в нижнем / левом подмассиве в место назначения , если имеет больше оставшихся элементов, чем верхний / правый подмассив:

for (;  i <= m;  ++i, ++k)

(3) Третий l oop копирует любые элементы в верхнем / правом подмассиве в пункт назначения , если , у него больше элементов, чем нижний / левый подмассив:

for (;  j <= r;  ++j, ++k)

(4) Четвертый l oop копирует из массива [temp] b обратно в исходный массив a:

for (i = l;  i <= r;  ++i, ++k)

Обратите внимание, что только один из l oop (2) или l oop (3) будет фактически копировать данные. Это потому, что l oop (1) гарантировал, что i <= m или j <= r будет false после того, как это будет сделано.

В вашем исходном коде , ваши первые два цикла [просто] копируются из подмассивов low / high в пределах a в b. Затем вы сливаетесь из b обратно в a [в три цикла].

В модифицированном коде мы объединяемся из a в b [в первых трех циклах]. Затем мы копируем обратно из массива [temp] b в a.

Итак, мы должны использовать временный массив. Но мы можем скопировать в него с самого начала. Или , мы можем скопировать его в конце. Любой подход будет работать.

И помните, что я упоминал, что массив b индексируется с нуля. Это позволило на один меньше l oop (четыре против пяти)