2
\$\begingroup\$

I've created a program that shows the time needed to sort a random array of integers. An example is:

user@computer:~/projects/sortc$ ./sortc 50000
Naive sort:      4.501963s
Bubble sort:     5.769375s
Insert sort:     1.969153s
Quick sort:      2.161162s

I implemented in C the common sort algorithms: insert, quick, bubble and naive (also called as selection sort). The purpose of the program is only to test these algorithms.

The source code is:

main.c

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

#include "utils.h"
#include "sort.h"

int check_sort(const unsigned long dim);

int main(int argc, char *argv[])
{
        if (argc != 2) {
                fprintf(stderr, "Usage: 'sortc <number>'\n");
                return -1;
        }

        long dim = strtol(argv[1], NULL, 0);

        if (dim <= 0) {
                fprintf(stderr, "The number must be positive.\n");
                return -1;
        }

        return check_sort((unsigned long) dim);
}

int check_sort(const unsigned long dim)
{
        int *naive = gen_array(dim), retval = -1;

        if (!naive) {
                fprintf(stderr, "Can't allocate memory for 'naive'.\n");
                return -1;
        }

        int *bubble = duplicate(naive, dim);

        if (!bubble) {
                fprintf(stderr, "Can't duplicate 'naive' for 'bubble'.\n");
                goto free_naive;
        }

        int *insert = duplicate(naive, dim);
        if (!insert) {
                fprintf(stderr, "Can't duplicate 'naive' for 'insert'.\n");
                goto free_bubble;
        }

       int *quick = duplicate(naive, dim);
       if (!quick) {
               fprintf(stderr, "Can't duplicate 'naive' for 'quick'.\n");
               goto free_insert;
       }

       float start_time = (float) clock() / CLOCKS_PER_SEC;
       naive_sort(naive, dim);
       float end_time = (float) clock() / CLOCKS_PER_SEC;

       end_time -= start_time;

       printf("Naive sort:\t %fs\n", end_time);

       start_time = (float) clock() / CLOCKS_PER_SEC;
       bubble_sort(bubble, dim);
       end_time = (float) clock() / CLOCKS_PER_SEC;

       end_time -= start_time;

       printf("Bubble sort:\t %fs\n", end_time);

       start_time = (float) clock() / CLOCKS_PER_SEC;
       insert_sort(insert, dim);
       end_time = (float) clock() / CLOCKS_PER_SEC;

       end_time -= start_time;

       printf("Insert sort:\t %fs\n", end_time);

       start_time = (float) clock() / CLOCKS_PER_SEC;
       quick_sort(quick, 0, dim - 1);
       end_time = (float) clock() / CLOCKS_PER_SEC;

       end_time -= start_time;

       printf("Quick sort:\t %fs\n", end_time);

       free(quick);
       retval = 0;

       free_bubble:
               free(bubble);
       free_insert:
                free(insert);
       free_naive:
                free(naive);

        return retval;
}

utils.h

#ifndef SRC_UTILS_H
#define SRC_UTILS_H

#include <time.h>
#include <stdlib.h>
#include <string.h>

/* It generates an array with random numbers.
 * Parameter:
 *      - const unsigned long dim: the array's dimension.
 * Return value: the array or NULL in case of error.
 */
int *gen_array(const unsigned long dim);

/* It duplicates an array.
 * Parameters:
 *      - int v[]: the array to duplicate;
 *      - const unsigned long dim: the array's dimension.
 * Return value: the new array or NULL in case of error.
 */
int *duplicate(int v[], const unsigned long dim);

/* It swaps two numbers.
 * Parameters:
 *      - int *a: the first number;
 *      - int *b: the second number.
 */
void swap(int *a, int *b);

#endif /* SRC_UTILS_H */

utils.c

#include "utils.h"

int *gen_array(const unsigned long dim)
{
        int *v = calloc(dim, sizeof(int));

        if (!v)
                return NULL;

        srand(time(NULL));

        for (unsigned long i = 0; i < dim; i++)
                v[i] = rand();

        return v;
}

int *duplicate(int v[], const unsigned long dim)
{
        if (!dim)
                return NULL;

        int *new = calloc(dim, sizeof(*v));

        if (!new)
                return NULL;

        return memcpy(new, v, dim);
}

void swap(int *a, int *b)
{
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

sort.h

#ifndef SRC_SORT_H
#define SRC_SORT_H

#include <stdbool.h>

#include "utils.h"

/* Sort an array using naive sort.
 * Parameters:
 *      - int v[]: the array;
 *      - unsigned long dim: the array's size.
 */
void naive_sort(int v[], unsigned long dim);

/* Sort an array using bubble sort.
 * Parameters:
 *      - int v[]: the array;
 *      - const unsigned long dim: the array's size.
 */
void bubble_sort(int v[], const unsigned long dim);

/* Sort an array using insert sort.
 * Parameters:
 *      - int v[]: the array;
 *      - const unsigned long dim: the array's size.
 */
void insert_sort(int v[], const unsigned long dim);

/* Sort an array using quick sort.
 * Parameters:
 *      - int v[]: the array;
 *      - const unsigned long first: the left extremity;
 *      - const unsigned long last: the right extremity.
 * Note: if you call this function for the first time, you should set 'first' to
 * zero and 'last' to array's size - 1.
 */
void quick_sort(int v[], const unsigned long first, const unsigned long last);

#endif /* SRC_SORT_H */

sort.c

#include "sort.h"

void naive_sort(int v[], unsigned long dim)
{
        unsigned long tmp, i;

        while (dim > 0) {
                i = tmp = 0;
                while (i < dim) {
                        if (v[i] > v[tmp])
                                tmp = i;

                        i++;
                }

                swap(&v[--dim], &v[tmp]);

        }
}

void bubble_sort(int v[], const unsigned long dim)
{
        bool swapped;

        do {
                swapped = false;
                for(unsigned long i = 0; i < (dim - 1); i++) {
                        if (v[i] > v[i + 1]) {
                                swap(&v[i], &v[i + 1]);
                                swapped = true;
                        }
                }
        } while (swapped);
}

void insert_sort(int v[], const unsigned long dim)
{
        unsigned long j;
        int tmp;

        for (unsigned long i = 1; i < dim; i++) {
                tmp = v[i];
                j = i - 1;
                while (j > 0 && v[j] > tmp) {
                        v[j + 1] = v[j];
                        j--;
                }
                v[j + 1] = tmp;
        }
}

void quick_sort(int v[], const unsigned long first, const unsigned long last)
{
        int key = v[first];
        unsigned long i = first + 1, j = last;

        if (first < last) {
                while (i < j) {
                        while (i < j && v[j] >= key)
                                j--;
                        while (i < j && v[i] <= key)
                                i++;
                        if (i < j)
                                swap(&v[i], &v[j]);
                }

                if (v[first] > v[i]) {
                        swap(&v[first], &v[i]);
                        quick_sort(v, first, i - 1);
                        quick_sort(v, i + 1, last);
                } else {
                        quick_sort(v, first + 1, last);
                }
        }
}

Makefile

.PHONY = clean all

VPATH = src

PROGNAME = sortc

SHELL = /bin/sh

CC ?= gcc

CFLAGS = -Wall -Wextra

OBJECTIVES = main.o utils.o sort.o

all : $(OBJECTIVES)
    $(CC) -o $(PROGNAME) $^

clean :
    $(RM) *.o $(PROGNAME)
\$\endgroup\$
4
\$\begingroup\$

Code duplication

In the check_sort, function, you do the same thing for each sorting algorithm:

  • copy an array
  • check if it has been successfully copied
  • measure the time it takes to sort the array
  • print the time
  • free the array

You can get rid of code duplication. Just create a separate function that takes a pointer to the beginning of the array, the number of elements of the array, a pointer to the sort function and its name (for printing custom error messages) and then call it for all sorting algorithms you have.

Separation of concerns

In fact, this function still does too much. It measures the execution time and does some logging. One function should do one thing. If the description of what the function does contains the word "and", it's a strong hint that it should be split into several smaller focused functions. I'd split it into to parts: benchmarking the code and logging. They are completely independent.

Naming and documentation

While it's OK for a small project like this one, "utils" isn't a good name in general. It might be fine, but files named "utils.*" often end up stuffed with tons of unrelated code and turn into garbage. Call it what it is. If it's responsible for generating and copying arrays, name it correspondingly.

Correctness

Your quick sort function doesn't work for an empty array. It tries to access the first element, which results in undefined behavior.

Consistency

All functions except for the quick_sort take an array and its size. It would be better if so did the quick_sort (you can wrap with a helper function to reuse the current implementation). It would also make the API more convenient: the user won't need to think if first and last must be inclusive.

\$\endgroup\$
4
\$\begingroup\$

Bug

When I saw your results, I was skeptical that insertion sort would be faster than quick sort. The problem is that there is a bug in this line in duplicate():

    return memcpy(new, v, dim);

This line should have been:

    return memcpy(new, v, dim * sizeof(*v));

Due to this bug, only the first 25% of the original array was being duplicated, and the rest was left filled with zeroes. This definitely would have an effect on the sorting times of your various sorts. Here are the times I got before and after I fixed the above line:

Before the fix (50000 elements)
-------------------------------
Naive sort:      0.718000s
Bubble sort:     0.905000s
Insert sort:     0.296000s
Quick sort:      0.406000s

After the fix (50000 elements)
------------------------------
Naive sort:      0.733000s
Bubble sort:     3.978000s
Insert sort:     0.359000s
Quick sort:      0.015000s
\$\endgroup\$
1
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy