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);
}
}
qsortthat 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\$buffervariable. 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 ofbubblesortitself, and while you getO(n^2)calls tomallocandfreein the naive implementation,memswapitself 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\$charwould 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\$