CSC161 2010F Imperative Problem Solving

Assignment 7: Sorting Out Sorting, Again

Assigned: Friday, 5 November 2010
Due: 11:00 p.m., Wednesday, 10 November 2010
Revised due date: 7:00 p.m. Friday, 12 November 2010

This assignment is also available in PDF.

Summary: In this assignment, you will experiment with sorting and with ways of writing somewhat generic code in C.

Purposes: To ground your learning of some sorting algorithms. To give you experience with a useful C technique.

Expected Time: Three to four hours.

Collaboration: I encourage you to work in groups of two or three students. However, you may work on your own or in groups of up to size four. You may discuss the assignment with anyone you wish, provided you clearly document such discussions.

Submitting: Email me a tarball of your important files (your .c files, your .h files, your Makefile, and anything else you deem appropriate).

Warning: So that this assignment is a learning experience for everyone, I may spend class time publicly critiquing your work.

Writing Generic Code in C

As we saw in a recent class, because C is typed, it is difficult to write generic code in C. However, it is not impossible. In particular, if we create a .c file that relies on some definitions for types and names, then we can set those types and names differently, to obtain different versions of the same program.

For example, consider the problem of swapping two values in an array. We've written a procedure to swap two elements in an array of integers as follows.

int_aswap (int a[], int i, int j)
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
} // int_aswap

Similarly, if we wanted to write something to swap two values in an an array of doubles, we might write

double_aswap (double a[], int i, int j)
  double temp = a[i];
  a[i] = a[j];
  a[j] = temp;
} // double_aswap

Note that these procedures differ only in (1) the prefix we apply to aswap, (2) the declaration of a, and the declaration of temp. We might therefore write a generic version of this as follows, with the understanding that a programmer can substitute in the type and prefix.

/** swap-generic.c *//
PREFIX(aswap) (TYPE a[], int i, int j)
  TYPE temp = a[i];
  a[i] = a[j];
  a[j] = temp;
} // generic awap

Why did we use PREFIX rather than TYPE? Because in some cases, the type may not match the prefix we want to use. For example, for strings, we might want the prefix to be string_, but the type will be char *.

Now, here's a cool thing. We can use the C preprocessor to take the place of the programmer. In particular, we can define PREFIX to put the float_ (or whatever) on the front, and TYPE to be float (or whatever). So, in order to get float_aswap, we just write

/** float-swap.c */
#define PREFIX(FUN) float_ ## FUN
#define TYPE float
#include "generic-swap.c"

The C pre-processor will then automatically turn this into

float_aswap (float a[], int i, int j)
  float temp = a[i];
  a[i] = a[j];
  a[j] = temp;

You can try this yourself. The files are in the example directory.


As we've discussed, there are a wide variety of sorting algorithms. Some of the more efficient sorting algorithms rely on a divide and conquer strategy. For example, in merge sort, we divide the array into two halves, sort the two halves, and then merge them together into a single sorted array. Similarly, in Quicksort, we rearrange the elements into small and large elements using a random pivot, sort the two halves, and we're done.


Your job is to build a variety of files that use the generic technique to implement three sorting routines (merge sort, Quicksort, and one sorting routine of your choice) for three types (integers, doubles, and strings).

In particular, you should create the following files:



Sunday, 7 November 2010 [Samuel A. Rebelsky]

  • Created.

Monday, 8 November 2010 [Samuel A. Rebelsky]

  • Minor cleanup.


Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Thu Nov 11 21:20:47 2010.
The source to the document was last modified on Thu Nov 11 20:24:09 2010.
This document may be found at

Samuel A. Rebelsky,