John Bowers

Lab 13

Wed, Sep 30, 2015

Sorting Lab

Objectives

The goal of this lab is to gain experience with the implementation of standard sorting algorithms.

Introduction

Download the lab starter files here:

Don’t forget to download and customize your machine-specific makefile and add sort.o to the MODS line.

In the main.c file, you will find a lot of code infrastructure for testing sorting routines, both for correctness and for efficiency. The exact implementations of the testing framework in main.c are interesting but not really relevant for this lab. One particularly-interesting aspect is the use of function pointers.

(Optional) Function Pointers

A function pointer is exactly what it sounds like: a pointer to a function. This may seem a bit odd but after this much time working with pointers in C you sould be unsurprised to learn that you can have a pointer to a function.

After all, the compiler must store the compiled code for each function somewhere in memory, and that location must have an address. That address is essentially a pointer to the function. The C language allows you to manipulate such pointers just like any other pointers, although the syntax is a bit more complicated.

If you look in main.h, you will find the following typedef:

typedef void(*sort)(int[], size_t);

This creates a typedef called sort that is a function pointer type. You’ll notice that all of the sorting functions have the same general signature:

void bubble_sort    (int items[], size_t n);
void selection_sort (int items[], size_t n);
void insertion_sort (int items[], size_t n);
void merge_sort     (int items[], size_t n);
void quick_sort     (int items[], size_t n);

This allows us to write code that exercises a generic sort function:

void do_performance_test(int items[], size_t n, sort f)
{
    double sum_time = 0.0;

    // run several trials and average the results
    for (size_t i = 0; i < NUM_TRIALS; i++) {

        // (OMITTED: set up test and begin timer)

        f(citems, n);    // call the sort function

        // (OMITTED: clean up and update sum)
    }

    // print results
    printf(" %12lu %12.4f\n", n, (sum_time / NUM_TRIALS));
}

In the above code, f is a function pointer parameter to the do_performance_test function. Its value represents the address of a sort function, and the key benefit is that we can pass ANY sort function that matches the sort type into do_performance_test and it will work.

This allows us to store the sort function pointers in an array and iterate over them:

sort all_sorts[] = {
    bubble_sort,
    selection_sort,
    insertion_sort,
    merge_sort,
    quick_sort
};

...

void do_all_performance_tests(int items[], size_t n)
{
    // run every sort
    for (size_t i = 0; i < NUM_SORTS; i++) {
        do_performance_test(items, n, all_sorts[i]);
    }
}

Some of the above code has been simplified a bit for presentation here, but the actual code isn’t much more complicated. We encourage you to look it over when you get a chance. Feel free to ask questions on Piazza if you see anything you don’t understand.

Furthermore, if you are intrigued by this concept, we encourage you to explore programming languages that include robust support for first-class functions. You will also see this topic again in CS430 (Programming Languages).

For the purposes of this lab, however, you should focus your attention on writing the sorting routines in sort.c.

Swapping Items

You may find the following macro useful, and we have provided it at the top of sort.c:

#define SWAP(A,I,J) int tmp = (A)[(I)]; (A)[(I)] = (A)[(J)]; (A)[(J)] = tmp;

You can use this macro to swap two elements at indices i and j in array items, using code like this:

    SWAP(items, i, j);

Comparing Items

We have provided the following function to compare data_t items:

int cmp(data_t a, data_t b)
{
    return a - b;
}

This function compares integers and returns a value that can be compared against zero to determine the order of the parameters:

(cmp(a,b)  < 0)  if  a < b
(cmp(a,b) == 0)  if  a = b
(cmp(a,b)  > 0)  if  a > b

For instance, instead of writing this:

    if (items[i] < items[j]) do_something();

You should write this:

    if (cmp(items[i], items[j]) < 0) do_something();

This makes your sorting functions more generic, and is vaguely reminiscent of iterators. Later (in PA 4), we will change data_t to be a pointer to a record data type. If you write your sorting functions to use the cmp comparison function, you will only need a new implementation for the cmp function and your sorting routines should still work!

Exercises