I've been implementing the mergesort algorithm in C, based on a dynamic array structure. I followed the pseudo-code step by step but I am not getting to the point. Here's how I have defined my structure and how I create and initialize it:
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;
}
And here is the implementation of the 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;
}
When I call the function on an array such as [18, 14, 20, 16, 12] I get the same identical array. I have tried adding some printf()
in the mergesort function and I discovered that it seems to slice the array correctly. So the problem must be in the dynarray_merge() function. The way I am checking if an element in the first array is greater than an element of the other one seems right to me, so I am totally stuck.
I am posting a compilable example of my code, to show you better what I mean.
#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);
}
The problem is how you compare the elements:
if (l->memory[i] < r->memory[j]) ...
Here, you are comparing pointers, not the values pointed to. You get these pointers from the malloc calls in main, which gave you ascending addresses.
Your implenentation of the dynamic array uses void * as type for the elements, so that it can be used for elements of any type. Your merge sort doesn't know which type is used and therefore can't know how to compare.
You can provide a callback function to the sorting function like qsort does:
typedef int VoidPointerCmp(const void *a, const void *b);
Then pass this function to your two merge sort functions:
void *dynarray_mergesort(dynarray *param, , VoidPointerCmp *cmp) ...
and compare your items like so:
if (cmp(l->memory[i], r->memory[j]) < 0) ...
A suitable comparison function for integers could look like this:
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;
}
In main, call:
dynarray_mergesort(a, int_cmp);
Some notes:
You allocate memory for each of the entries. This is not necessary. You can make the void pointers point at the elements of the existing arrays:
for (int i = 0; i < 5; i++) add_elem(a, &arr[i]);
Sorting will not affect the original array arr.
You don't free the allocated memory or destroy your dynamic arrays. You should probably write a destructor function for the dynamic arrays and clean up the temporary arrays l and r after using them.
I think that you don't use the used field correctly. You probably don't need it: It is enough to have the allocated size and current length of the array. (You can replace the index with the length.)