Setup

Register for the lab using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.

Sorting Arrays

In this lab, you will implement various algorithms which can benefit from using C abstractions to reduce code duplication. We’ll begin by writing functions that seem different and discover how to generalize across parameters, functions, and types. You’ve already seen most of these concepts, but this lab will teach you the C syntax for these patterns and reinforce noticing when these patterns exist.

Since this lab comes with a pre-made Makefile, we can use make main to compile our code, and then run it with ./main. Additionally, this lab comes with tests. To run them, use make test in the terminal.

Part 1: Write Some Sorts

Task 0. Write a function ascending_int_sort_whole which sorts the provided array in-place (i.e., you must edit the original array to be in order without allocating more than \(\mathcal{O}(1)\) scratch space) of ints in ascending (i.e., numbers are increasing) order. You must use either insertion sort or selection sort.

Task 1. Write a function ascending_int_sort which in-place sorts a sub-array of the provided array between \([\text{lo}, \text{hi})\) (i.e., between lo (inclusive) and hi (exclusive)) of ints in ascending order. You must use the same sorting algorithm as before.

Task 2. ascending_int_sort is a strict generalization of ascending_int_sort_whole. Go back and fix ascending_int_sort_whole to be a single call to ascending_int_sort. This should remove gobs of duplicated code.

Conclusion 1: Abstraction by Parameterization

One way of reducing duplicated code or redundancy is identifying argument parameterizations of the problem that allow us to generalize. That is, adding the right parameters can allow us to solve harder problems with approximately the same code.

Part 2: Writing More Sorts

Task 3. Write a function descending_int_sort which in-place sorts the provided array of ints in descending (i.e., numbers are decreasing) order. You must use the same sorting algorithm as before.

Interlude: Function Pointers

In C, we can make references to functions (i.e., “function pointers”), but the syntax is a bit wonky. The syntax allows us to pass around functions as values, which feels, in principle, like lambdas in Python and Java. Because the syntax is a bit hairy, we will always typedef away the definitions. A typical function pointer typedef looks like:

typedef RETURN_TYPE (*TYPE_NAME)(ARGUMENTS);

We will use function pointers primarily to generalize functions across types and orderings. Notably, there was a ton of redundancy between ascending_int_sort and descending_int_sort, because they’re effectively the same function. Just like before, we will add an argument to generalize the problem. This time, though, it will be a function pointer. We’ll do this in steps:

Introduce a function type to specify how to “compare” ints.
Define two functions that meet the type (one for ascending, and one for descending)
Write a more general function called int_sort which accepts one of these functions as an extra parameter

Interlude: `comparator_t`s

We say a function is a comparator_t if it specifies a total ordering (<) over a type by taking in two arguments of the same type (say, a and b) and returning an int \(X\) as follows:

If a < b, then \(X < 0\)
If a = b, then \(X = 0\)
If a > b, then \(X > 0\)

It is useful to compare this to Java’s definition of compareTo and compare: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Comparator.html

In contrast, we will define an int_comparator_t as a function pointer in C as follows: typedef int (*int_comparator_t)(int a, int b).

Task 4. Write a function int_sort which in-place sorts the provided array of ints according to a provided int_comparator_t. You must use the same sorting algorithm as before. You can call a function pointer using the normal func(...) syntax; you will want to check if the result is < 0.

Task 5. int_sort is a strict generalization of ascending_int_sort and descending_int_sort. Go back and fix ascending_int_sort and descending_int_sort to be a single call to int_sort. This should remove gobs of duplicated code. You will want to look in the comparator.{h,c} files to see which comparators are defined.

Conclusion 2: Abstraction by Functional Interfaces

One way of reducing duplicated code or redundancy is identifying functional parameterizations of the problem that allow us to generalize. That is, adding the right functions (as arguments) can allow us to solve more general problems with approximately the same code.

Part 3: Writing Even More Sorts

Task 6. Write a function string_sort which in-place sorts the provided array of char * according to a provided string_comparator_t. You must use the same sorting algorithm as before.

Interlude: `void *`

C does not have generics like Java does, but it does have a “generic pointer type” (that is, a pointer that points to an unspecified type) called void *. We can use (abuse?) this to get a mediocre substitute for generics (that is, abstraction over types). We’ll need to do two things to incorporate void *:

Generalize our idea of int_comparator_t and string_comparator_t to a single typedef for comparator_t that takes two void *’s instead of specific types.
Write a more general function called sort which accepts both a comparator_t argument as well as an array of void *’s.

Task 7. Write a function sort which in-place sorts the provided array of void * according to a provided comparator_t. You must use the same sorting algorithm as before.

Task 8. sort is a strict generalization of string_sort, but NOT of int_sort!! void *’s are POINTERS, but ints are VALUE types. We can, however, sort int *’s. (An aside: this is exactly why you need to use Integer instead of int in Java generics!)

Go back and fix string_sort to be a single call to sort. To silence the compiler warnings that come up, you will need to make casts to void ** and comparator_t in the obvious places. This should remove gobs of duplicated code.

Conclusion 3: Abstraction by Types

One way of reducing duplicated code or redundancy is identifying type parameterizations of the problem that allow us to generalize. That is, using generic types can allow us to solve more general problems with approximately the same code. This is particularly important when implementing data structures, because we don’t want to write code for each type we want a list for.

Getting Checked Off

Labs will be due the following Tuesday from when they are assigned, at 11:30 PST. You will need to get manually checked off for most labs, as we will not be using totally automated tests. To get checked off, make a ticket saying you are done, and we will check you off as soon as possible. Please include the link to your repo in the ticket.