Sorting algorithms and TFP in C

As mentioned yesterday the exercise form learn-c-the-hard-way was to write a couple of sorting algorithms. Unlike most of the previous exercises where the author asks the reader to copy the answers straight out of the book, this time it was to copy tests straigt out of the book, added them to the existing project, reading about bubble sort and merge sort on wikipedia, traslate the Pseudocode into code that will pass the tests.

I didn’t get it finished, but I id make quite a lot of progress and resolved some errors in the build process my Makefile was still trying to create shared objects so I was getting a few errors from the linker. Eventually though I got things work as expected, useful compilation errors, tests ran and failed.

Then I started working on getting one test to pass, wrote a few declinations in the header file that reflected the return values for and arguments types for the functions, and a type definition so functions can be passed as arguments. It was mostly a case of interpreting the expected behaviour from the tests and writing the declarations.

#ifndef list_algos_h
#define list_algos_h
#include <lcthw/list.h>

typedef int (*List_compare) (const char *a, const char *b);

int List_bubble_sort(List *list, List_compare compare_function);
List * List_merge_sort(List *list, List_compare compare_function);

#endif

From there I started to comment out some of the tests for functions which I was not working on at the time, this helped allot as the feed back from the tests run on non-existing units was a bit distracting. Eventually I got the bubble sort algorithm to pass one test, and then the next tests on the bubble sort algorithm two where easy enough. A bubble sort recursively compares adjacent pairs and maybe swaps them until no more swaps are done in an interaction.

I’ve still have the merge sort to do which guessing form the Wikipedia article will be a bit more complicated, but the pseudocode looks more useful.

Tips of reading this far

Instead of exiting vim :q to run a command, you can use the vim shell with :! [command].

examples :! make tests or :! fortune | cowsay

Written by Marc McIntosh Find him on github