В алгоритме merge_sort, он работает, когда параметр является списком двойного типа, но не когда это список типа int

Question

Я хочу отсортировать список типов int.но когда параметром в функции слияния является double список, это работает!но не тогда, когда это int список ...

Вот функция сортировки.параметр int указатель.

, если изменение списка int на список double работает нормально.

ex) int *a -> double *a

ex) int *l, *r1 -> double *l, *r1

ex) l = (int *)calloc(n1+1,sizeof(int)), r1 = (int *)calloc(n2+1,sizeof(int)) -> l = (double *)calloc(n1+1,sizeof(double)) r1 = (double *)calloc(n2+1,sizeof(double))

void merge(int *a, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int *l, *r1;
    int i, j, k;

    l = (int *)calloc(n1 + 1, sizeof(int));
    r1 = (int *)calloc(n2 + 1, sizeof(int));

    for (i = 0; i < n1;i++)
        l[i] = a[p + i];
    for (j = 0; j < n2; j++)
        r1[j] = a[q + 1 + j];

    l[n1] = 10000;
    r1[n2] = 10000;

    i = 0;
    j = 0;

    for (k = p; k <= r; k++) {
        if (l[i] <= r1[j]) {
            a[k] = l[i];
            ++i;
        } else {
            a[k] = r1[j];
            ++j;
        }
    }
    return;
}

здесь рекурсивная функция.Пока длина списка не будет 1

ex) int *a -> double *a

void merge_sort(int *a, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

Создайте список длины 10 и поместите его в функцию mergesort.Затем распечатайте список.

int main(int argc, char *argv[]) {

    int i, *a[10];

    for (i = 0; i < 10; i++) {
        a[i] = rand() % 10 + 1;  
    }

    merge_sort(a, 0, 10);

    for (i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

результат равен

0 0 0 2 5 10 9 9 3 5

Answer 1

В вашем коде несколько проблем:

• если вы хотите изменить тип элемента массива, вы должны изменить его везде, в том числе в функции main, а также вы должны изменить формат printf. Увеличение уровня предупреждения (gcc -Wall -Wextra -Werror) предотвратит глупые ошибки.
• неверное определение a в main, должно быть int a[10];, а не массив указателей на int.
• вы передаете общее количество элементов в mergesort() в main: merge_sort(a, 0, 10);, что означает, что r в сортировке слиянием должен быть исключен. Тогда рекурсивный вызов merge_sort(a, q + 1, r); в mergesort будет неправильным, поскольку q следует исключить в merge_sort(a, p, q);, но включить во вторую половину. Вместо этого используйте merge_sort(a, q, r);.
• Вы вычисляете середину сегмента с помощью int q = (p + r) / 2;. Вы можете иметь неопределенное поведение для больших массивов, так как q + r может выходить за пределы диапазона типа int. Это классическая ошибка, которая может оставаться незамеченной на протяжении десятилетий, пока кто-то не использует код для большого массива. Используйте int q = p + (r - p) / 2;, чтобы избежать этого.
• алгоритм в merge неверен: вы предполагаете, что все значения в массивах < 10000, что может быть неверным предположением. Код должен обрабатывать все возможные значения. Вам следует проверить индексные переменные, чтобы определить конец подмассивов и обработать оставшиеся значения другого массива, в частности.
• Вы не освобождаете массивы, выделенные в merge, что приводит к утечкам памяти.
• , чтобы упростить изменение типа элемента, вы можете использовать typedef.

Вот улучшенная версия:

#include <stdio.h>

#ifdef USE_DOUBLE
typedef double sorttype;
#else
typedef int sorttype;
#endif

void merge(sorttype *a, int p, int q, int r) {
    // merge subarrays a[p...q] and a[q...r]
    // upper bounds q and r are excluded
    int n1 = q - p;
    int n2 = r - q;
    sorttype *a1, *a2;
    int i, j, k;

    a1 = malloc(n1 * sizeof(*a1));
    a2 = malloc(n2 * sizeof(*a2));

    for (i = 0; i < n1; i++)
        a1[i] = a[p + i];
    for (j = 0; j < n2; j++)
        a2[j] = a[q + j];

    i = 0;
    j = 0;
    for (k = p; k < r; k++) {
        if (i < n1 && (j >= n2 || a1[i] <= a2[j])) {
            a[k] = a1[i];
            ++i;
        } else {
            a[k] = a2[j];
            ++j;
        }
    }
    free(a1);
    free(a2);
}

void merge_sort(sorttype *s, int p, int r) {
    if (r - p > 1) {
        int q = p + (r - p) / 2;
        merge_sort(s, p, q);
        merge_sort(s, q, r);
        merge(s, p, q, r);
    }
}

int main(int argc, char *argv[]) {

    sorttype a[10];
    int i;

    for (i = 0; i < 10; i++) {
        a[i] = 1 + rand() % 10;
    }

    merge_sort(a, 0, 10);

    for (i = 0; i < 10; i++) {
#ifdef USE_DOUBLE
        printf("%g ", a[i]);
#else
        printf("%d ", a[i]);
#endif
    }
    printf("\n");
    return 0;
}

Выход для int:

1 3 4 4 5 8 9 9 10 10

Выход для double:

1 3 4 4 5 8 9 9 10 10

Обратите внимание, что случайные числа идентичны, хотя программа была перекомпилирована и перезапущена ... Вы должны использовать srand(clock()), чтобы попытаться получить другую псевдослучайную последовательность.

Также обратите внимание, что выделение a2 для создания копии правого подмассива не требуется, поскольку операция объединения никогда не перезаписывает элементы из правой половины, которые еще не были скопированы.

Кроме того, вы должны проверить наличие ошибок выделения и сообщить об этом.

Вот улучшенная версия merge:

void merge(sorttype *a, int p, int q, int r) {
    // merge subarrays a[p...q] and a[q...r]
    // upper bounds q and r are excluded
    int n1 = q - p;
    int n2 = r - q;
    sorttype *a1;
    int i, j, k;

    a1 = malloc(n1 * sizeof(*a1));
    if (a1 == NULL) {
        fprintf(stderr, "memory allocation failure\n");
        exit(1);
    }
    for (i = 0; i < n1; i++)
        a1[i] = a[p + i];

    i = 0;
    j = 0;
    for (k = p; i < n1 && k < r; k++) {
        if (j >= n2 || a1[i] <= a[q + j]) {
            a[k] = a1[i];
            ++i;
        } else {
            a[k] = a[q + j];
            ++j;
        }
    }
    free(a1);
}