Return to Answer

• 1

• 87.9k
• 14
• 104
• 325

We can write a helper for check_sort():

int time_sort(const int *values, const size_t length,
 void (*sort_function)(int*,unsigned long),
 const char* name)
{
 int *copy = duplicate(values, length);
 if (!copy) {
 fprintf(stderr, "Can't allocate memory for '%s'.\n", name);
 return 1;
 }
 clock_t start_time = clock();
 sort_function(copy, length);
 clock_t end_time = clock();
 double elapsed = (double)(end_time - start_time) / CLOCKS_PER_SEC;
 printf("%s:\t %lfs\n", name, elapsed);
 free(copy);
 return 0;
}
int check_sort(const unsigned long dim)
{
 const int *v = gen_array(dim);
 int result = time_sort(v, dim, naive_sort, "naive")
 || time_sort(v, dim, bubble_sort, "bubble")
 || time_sort(v, dim, insert_sort, "insert")
 || time_sort(v, dim, quick_sort, "quick");
 free(v);
 return result;
}

I made a small tweak to the timing - by performing the subtraction in integers, and only converting to floating-point when we scale by CLOCKS_PER_SEC, we reduce errors. I've also used double rather than float - the latter is useful when many values are being stored, but there's little other benefit on most platforms (almost every system with floating-point hardware is as fast with double as with float).

You'll need to change the signature of quick_sort to agree with the other functions - I'll leave that as an exercise.

You could also add some verification that the sort has actually put the values into ascending order (within time_sort()):

for (size_t i = 0; i < length-1; ++i) {
 if (copy[i] >= copy[i+1]) {
 fprintf(stderr, "Not correctly sorted by '%s'!\n", name);
 break;
 }
}

We can reduce the amount of header inclusion.

utils.h doesn't need <time.h>, although utils.c might. In fact, it turns out that utils.c doesn't, either.

It's best to hange the order of includes to include our own headers before the standard library headers. This exposes any missing includes that the headers themselves require (usually just those that define the types used in those headers). Includes that are needed for the implementation should only be in the implementation files that need them.

Here's my (untested) assessment of what's required where:

###utils.h /* no includes / ###utils.c:
#include <stdlib.h> #include <string.h> ###sort.h / no includes */ ###sort.c #include "utils.h" #include <stdbool.h> ###main.c #include "utils.h" #include "sort.h" #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h>

In the headers themselves, there's no need to mention that dim is constant in declarations such as this:

int *duplicate(int v[], const unsigned long dim);

As dim is passed by value, how it's used within the implementation is not relevant to the caller. However, we can (and should) indicate that this method won't change the int values referenced by v; consider also using size_t rather than unsigned long to better indicate your intent:

int *duplicate(const int v[], size_t dim);
int *duplicate(const int v[], const size_t dim)
{
 /* implementation - here we do mark dim as constant */
}

We're allocating and zeroing memory with calloc(), but then immediately writing it. That's inefficient - we can simply allocate with malloc() if we know we'll be writing to it. It's also a good idea to use the element size of the variable we're assigning to, like this:

 int *new = malloc(dim * sizeof *new);

That way, it's easier to see that it's consistent (and if you ever change the type of new, the allocation size would automatically adjust).