I'm trying out different sorting algorithms for learning purposes, here I'm doing a "type-agnostic" bubbleaort.
I modeled the function signature after the standard library's qsort
. I know the bubblesort algorithm in general is not that fast, but I'm looking for a review in particular about the memory management.
In my implementation I'm accepting a void
pointer to an array, the size of the array, the size of the single elements and the pointer to the comparison function. Then I convert the void
pointers to char pointers, and I do manually the pointer arithmetics (I avoided nonstandard arithmetics on void *
).
The part I'm not very happy about is the need for a buffer (dynamically allocated), and the use of memcpy
to swap the memory of the two elements. I'd love to know if that part can be improved even slightly.
I'm using a pointer to the beginning and the end of the array, instead of using indexes with []
bracket notation.
Also, what about the if (buffer == NULL)
check and "halting" with exit()
? Is there a more elegant way to fail here?
I also could use one variable instead of two (current and left), but doing one more pointer arithmetic in the inner loop.
Here's my current bubblesort implementation:
/**
* Bubblesort algorithm. Compatible with any data type.
* @param base A void pointer to the array's first element.
* @param num The number of elements in the array.
* @param size The size of the data type.
* @param compar A pointer to the comparison function.
*/
void bubblesort(void* base, size_t num, size_t size,
int (*compar)(const void*, const void*)
) {
const char *arr = (const char *) base;
char *buffer, *left, *current, *right;
if (arr != NULL && size > 0 && num > 1) {
buffer = (char *) malloc(size);
if (buffer == NULL) {
fprintf(stderr, "Out of memory.");
exit(EXIT_FAILURE);
}
right = (char *) arr + num * size;
while (right > arr) {
left = (char *) arr;
current = left + size;
while (current < right) {
// Compare the two elements and move the bigger to the right
if (compar(left, current) > 0) {
memcpy(buffer, left, size); // Temporary variable
memcpy(left, current, size); // Swap pt.1
memcpy(current, buffer, size); // Swap pt.2
}
left += size;
current += size;
}
right -= size;
}
free(buffer);
}
}
qsort
that accepts an "array" as a pointer to the first element of the array. That function won't work with a list of pointers. If I want to pass a list of pointers instead, that would be a different function signature, with a different implementation. Here my own "requirement" is to "mimic" a possible standard library function. \$\endgroup\$buffer
variable. In any case, it just occurred to me that you could isolate the threememcpy
, together with the buffer allocation and release, to its own functionmemswap
. This increases readability ofbubblesort
itself, and while you getO(n^2)
calls tomalloc
andfree
in the naive implementation,memswap
itself could be optimised to use the stack as a buffer (for smallsize
), or use no buffer at all (swap word by word). You might even want to take a peek at C++'sswap_ranges
. \$\endgroup\$char
would then usually be allocated to a CPU register rather than stack memory or heap memory, but again: C doesn't really know the difference). \$\endgroup\$