Получение странных результатов в алгоритме сортировки слиянием [C]

Question

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

typedef struct dynarray {
    void **memory;
    size_t allocated;
    size_t used;
    int index;
} dynarray;

//creates a new, empty, dynarray
void create_dynarray(dynarray **array, size_t size) {
    *array = calloc(size, sizeof **array);
    (*array)->memory = NULL;
    (*array)->allocated = 0;
    (*array)->used = 0;
    (*array)->index = -1;
}

А вот реализация mergesort:

//function used to slice the dynarray in two subarrays and call merge function
void *dynarray_mergesort(dynarray *param) {
    if (dynarray_length(param) > 1) {
        size_t size = param->used / sizeof(void*);  
        size_t m = size / 2;
        size_t n = size - size / 2;
        struct dynarray *l; 
        create_dynarray(&l, m);
        struct dynarray *r;
        create_dynarray(&r, n);  

        for (size_t i = 0 ; i < m; i++) {
            add_elem(l, param->memory[i]);
        }
        for (size_t j = m; j < size; j++) {
            add_elem(r, param->memory[j]);
        }

        dynarray_mergesort(l);
        dynarray_mergesort(r);
        dynarray_merge(param, l, r, size);
    }  
    return param;
}

//function used to mergesort the array
void *dynarray_merge(dynarray *param, dynarray *l, dynarray *r, int size) {
    int i = 0,j = 0, k = 0; 
    while (i < size/2 && j < size - size / 2) {
        if (l->memory[i] < r->memory[j]) {
            param->memory[k] = l->memory[i];  
            i++;
            k++;
        } else {     
            param->memory[k] = r->memory[j];
            j++;
            k++;      
        }
    }
    while (i < size / 2) {
        param->memory[k] = l->memory[i];
        i++;
        k++;
    }
    while (j < size - size / 2) {
        param->memory[k] = r->memory[j];
        j++;
        k++;
    }
    return param;
}

Когда я вызываю функцию в массиве например [18, 14, 20, 16, 12] Я получаю такой же идентичный массив. Я попытался добавить printf() в функцию слияния, и обнаружил, что, похоже, правильно нарезает массив. Так что проблема должна быть в функции dynarray_merge(). То, как я проверяю, больше ли элемент в первом массиве, чем элемент другого, мне кажется правильным, поэтому я застрял.

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

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

typedef struct dynarray {
    void **memory;
    size_t allocated;
    size_t used;
    int index;
} dynarray;

//creates a new, empty, dynarray
void create_dynarray(dynarray **array, size_t size) {
    *array = calloc(size, sizeof **array);
    (*array)->memory = NULL;
    (*array)->allocated = 0;
    (*array)->used = 0;
    (*array)->index = -1;
}

//adds a new element at the bottom of dynarray
void add_elem(dynarray *array, void *data) {
    size_t toallocate;
    size_t size = sizeof(void *);
    if ((array->allocated - array->used) < size) { // if M - N ...
        toallocate = array->allocated == 0 ? size : (array->allocated * 2);
        array->memory = realloc(array->memory, toallocate);
        array->allocated = toallocate;
    }

    array->memory[++array->index] = data;
    array->used = array->used + size;
}

//get length of the dynarray
int dynarray_length(dynarray *array) {
    return array->index + 1;
}

//retrieves an element in a specific position of the dynarray
void *get_i_elem(dynarray *array, int index) {
    if (index < 0 || index > array->index)
        return NULL;

    return array->memory[index];
}

//function used to mergesort the array
void *dynarray_merge(dynarray *param, dynarray *l, dynarray *r, int size) {
    int i = 0,j = 0, k = 0;    
    while (i < size/2 && j < size - size / 2) {
        if (l->memory[i] < r->memory[j]) {
            param->memory[k] = l->memory[i];  
            i++;
            k++;
        } else {
            param->memory[k] = r->memory[j];
            j++;
            k++;    
        }
    }
    while (i < size / 2) {
        param->memory[k] = l->memory[i];
        i++;
        k++;
    }
    while (j < size - size / 2) {
        param->memory[k] = r->memory[j];
        j++;
        k++;
    }
    return param;
}

//function used to slice the dynarray in two subarrays and call merge function
void *dynarray_mergesort(dynarray *param) {
    if (dynarray_length(param) > 1) {
        size_t size = param->used / sizeof(void*);  
        size_t m = size / 2;
        size_t n = size - size / 2;
        struct dynarray *l; 
        create_dynarray(&l, m);
        struct dynarray *r;
        create_dynarray(&r, n);  

        for (size_t i = 0 ; i < m; i++) {
            add_elem(l, param->memory[i]);
        }
        for (size_t j = m; j < size; j++) {
            add_elem(r, param->memory[j]);
        }

        dynarray_mergesort(l);
        dynarray_mergesort(r);
        dynarray_merge(param, l, r, size);
    }  
    return param;
}

//print arrays, useful to test 
void print_array(dynarray *array) {
    for (int i = 0; i < dynarray_length(array); i++) {
        printf("%d\t", *(int *)get_i_elem(array, i));
        //puts("");
    }
}

int main() {
    struct dynarray *a;
    create_dynarray(&a, 5);
    int arr[5] = { 18, 14, 20, 16, 12};
    int *ap = malloc(sizeof(int));
    int *bp = malloc(sizeof(int));
    int *cp = malloc(sizeof(int));
    int *dp = malloc(sizeof(int));
    int *ep = malloc(sizeof(int));
    *ap = arr[0];
    *bp = arr[1];
    *cp = arr[2];
    *dp = arr[3];
    *ep = arr[4];
    add_elem(a, ap);
    add_elem(a, bp);
    add_elem(a, cp);
    add_elem(a, dp);
    add_elem(a, ep);
    printf("\nbefore mergesort\n");
    print_array(a);
    puts("");
    printf("\nafter mergesort\n");
    dynarray_mergesort(a);
    print_array(a);
}

Answer 1

Проблема в том, как вы сравниваете элементы:

if (l->memory[i] < r->memory[j]) ...

Здесь вы сравниваете указатели, а не значения, на которые указывают. Вы получаете эти указатели из вызовов malloc в main, которые дали вам восходящие адреса.

Ваше расширение массива динамического c использует void * как тип для элементов, так что он может использоваться для элементов любого типа. Ваша сортировка слиянием не знает, какой тип используется, и поэтому не может знать, как сравнивать.

Вы можете предоставить функцию обратного вызова для функции сортировки, как qsort делает:

typedef int VoidPointerCmp(const void *a, const void *b);

Затем передайте эту функцию вашим двум функциям сортировки слиянием:

void *dynarray_mergesort(dynarray *param, , VoidPointerCmp *cmp) ...

и сравните ваши элементы следующим образом:

if (cmp(l->memory[i], r->memory[j]) < 0) ...

Подходящая функция сравнения для целых чисел может выглядеть следующим образом:

int int_cmp(const void *pa, const void *pb)
{
    const int *a = pa;
    const int *b = pb;

    if (*a < *b) return -1;
    if (*a > *b) return 1;
    return 0;
}

В main звоните:

dynarray_mergesort(a, int_cmp);

Некоторые примечания:

• Вы выделяете память для каждой из записей. Это не обязательно. Вы можете указать указатели void на элементы существующих массивов:

  for (int i = 0; i < 5; i++) add_elem(a, &arr[i]);
  

  Сортировка не повлияет на исходный массив arr.

• Вы не t освободить выделенную память или уничтожить ваши динамические c массивы. Вам, вероятно, следует написать функцию-деструктор для динамических c массивов и очистить временные массивы l и r после их использования.

• Я думаю, что вы этого не делаете используйте поле used правильно. Возможно, вам это не нужно: достаточно иметь выделенный размер и текущую длину массива. (Вы можете заменить указатель на длину.)