[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Function pointers. Readings: KernighanRitchie Section 5.11, C/FunctionPointers.

In lecture I told lurid stories of the horrifying complexity of the implementation of qsort in the GNU C library. In fact, it's not that bad, weighing in at only 240 lines of code, not counting comments. But in that 240 lines it does choose between four different sorting routines involving three different sorting algorithms, including two versions of mergesort (depending on whether the objects are aligned on word boundaries, which allows for faster copying), quicksort (if there is not enough free memory to allocate the extra storage needed for mergesort), and insertion sort (when the inputs to quicksort get small enough).

Here are the actual source files: msort.c, qsort.c. Note that qsort is actually in msort.c.


2014-06-17 11:58