ex35.tex

\chapter{Exercise 35: Sorting And Searching}

In this exercise I'm going to cover four sorting algorithms and one
search algorithm.  The sorting algorithms are going to be quick sort,
heap sort, merge sort, and radix sort.  I'm then going to show you
how to binary search after you've done a radix sort.

However, I'm a lazy guy, and in most standard C libraries you have existing
implementations of the heapsort, quicksort, and mergesort algorithms.  Here's
how you use them:

\begin{code}{src/lcthw/darray\_algos.c}
<< d['code/liblcthw/src/lcthw/darray_algos.c|pyg|l'] >>
\end{code}

That's the whole implementation of the \file{darray\_algos.c} file, and it
should work on most modern Unix systems.  What each of these does is sort the
\ident{contents} store of void pointers using the \ident{DArray\_compare} you
give it.  I'll show you the header file for this too:

\begin{code}{src/lcthw/darray\_algos.h}
<< d['code/liblcthw/src/lcthw/darray_algos.h|pyg|l'] >>
\end{code}

About the same size and should be what you expect.  Next you can see how these
functions are used in the unit test for these three:

\begin{code}{tests/darray\_algos\_tests.c}
<< d['code/liblcthw/tests/darray_algos_tests.c|pyg|l'] >>
\end{code}

The thing to notice, and actually what tripped me up for a whole day, is
the definition of \ident{testcmp} on line 4.  You have to use a \verb|char **|
and \emph{not} a \verb|char *| because qsort is going to give you a pointer
to \emph{the pointers} in the \ident{contents} array.  The reason is qsort
and friends are scanning the array, and handing \emph{pointers} to each element
in the array to your comparison function.  Since what I have in the \ident{contents}
array is pointers, that means you get a pointer to a pointer.

With that out of the way you have to just implemented three difficult 
sorting algorithms in about 20 lines of code.  You could stop there,
but part of this book is learning how these algorithms work so the
extra credit is going to involve implementing each of these.


\section{Radix Sort And Binary Search}

Since you're going to implement quicksort, heapsort, and mergesort on your own,
I'm going to show you a funky algorithm called Radix Sort.  It has a
slightly narrow usefulness in sorting arrays of integers, and seems to
work like magic.  In this case I'm going to create a special data 
structure called a \ident{RadixMap} that is used to map one integer
to another.

Here's the header file for the new algorithm that is both algorithm
and data structure in one:

\begin{code}{src/lcthw/radixmap.h}
<< d['code/liblcthw/src/lcthw/radixmap.h|pyg|l'] >>
\end{code}

You see I have a lot of the same operations as in a \ident{Dynamic Array} or
a \ident{List} data structure, the difference is I'm working only with
fixed size 32 bit \ident{uin32\_t} integers.  I'm also introducing you to
a new C concept called the \ident{union} here.

\subsection{C Unions}

A union is a way to refer to the same piece of memory in a number of different
ways.  How they work is you define them like a \ident{struct} except every
element is sharing the same space with all of the others.  You can think
of a union as a picture of the memory, and the elements in the union as 
different colored lenses to view the picture.

What they are used for is to either save memory, or to convert chunks of memory
between formats.  The first usage is typically done with "variant types", where
you create a struct that has "tag" for the type, and then a union inside it
for each type.  When used for converting between formats of memory, you simply
define the two structures, and then access the right one.

First let me show you how to make a variant type with C unions:

\begin{code}{ex35.c}
<< d['code/ex35.c|pyg|l'] >>
\end{code}

You find this in many implementations of dynamic languages.  The language will
define some base variant type with tags for all the base types of the language,
and then usually there's a generic "object" tag for the types you create.
The advantage of doing this is that the \ident{Variant} only takes up as much
space as the \ident{VariantType type} tag and the largest member of the 
union.  This is because C is "layering" each element of the \ident{Variant.data}
union together so they overlap, and to do that it sizes it big enough to
hold the largest element.

In the \file{radixmap.h} file I have the \ident{RMElement} union which
demonstrates using a union to convert blocks of memory between types.  In
this case, I want to store a \ident{uint64\_t} sized integer for sorting
purposes, but I want a two \ident{uint32\_t} integers for the data to
represent a \ident{key} and \ident{value} pair.  By using a union I'm
able to access the same block of memory in the two different ways
I need cleanly.

\subsection{The Implementation}

I next have the actual \ident{RadixMap} implementation for each of these
operations:

\begin{code}{src/lcthw/radixmap.c}
<< d['code/liblcthw/src/lcthw/radixmap.c|pyg|l'] >>
\end{code}

As usual enter this in and get it working along with the unit test
then I'll explain what's happening.  Take \emph{special} care with the
\ident{radix\_sort} function as it's very particular in how it's
implemented.

\begin{code}{tests/radixmap\_tests.c}
<< d['code/liblcthw/tests/radixmap_tests.c|pyg|l'] >>
\end{code}

I shouldn't have to explain too much about the test.  It's simply 
simulating placing random integers into the \ident{RadixMap} and then
making sure it can get them out reliably.  Not too interesting.

In the \file{radixmap.c} file most of the operations are easy to understand
if you read the code.   Here's a description of what the basic functions
are doing and how they work:

\begin{description}
\item[RadixMap\_create] As usual I'm allocating all the memory needed for
    the structures defined in \file{radixmap.h}.  I'll be using the 
    \ident{temp} and \ident{contents} later when I talk about \ident{radix\_sort}.
\item[RadixMap\_destroy] Again, just destroying what was created.
\item[radix\_sort] The meat of the data structure, but I'll explain what
    it's doing in the next section.
\item[RadixMap\_sort] This uses the \ident{radix\_sort} function to actually
    sort the \ident{contents}.  It does this by sorting between the \ident{contents}
    and \ident{temp} until finally \ident{contents} is sorted.  You'll see how
    this works when I describe \ident{radix\_sort} later.
\item[RadixMap\_find] This is using a binary search algorithm to find a key
    you give it.  I'll explain how this works shortly.
\item[RadixMap\_add] Using the \ident{RadixMap\_sort} function, this will
    add the key and value you request at the end, then simply sort it again
    so that everything is in the right place.  Once everything is sorted,
    the \ident{RadixMap\_find} will work properly because it's a binary search.
\item[RadixMap\_delete] Works the same as \ident{RadixMap\_add} except "deletes"
    elements of the structure by setting their values to the max for a unsigned
    32 bit integer, \ident{UINT32\_MAX}.  This means you can't use that value
    as an key value, but it makes deleting elements easy.  Simply set it to
    that and then sort and it'll get moved to the end.  Now it's deleted.
\end{description}

Study the code for the ones I described, and then that just leaves
\ident{RadixMap\_sort}, \ident{radix\_sort}, and \ident{RadixMap\_find}
to understand.

\subsection{RadixMap\_find And Binary Search}

I'll start with how the binary search is implemented.  Binary search is 
simple algorithm that most people can understand intuitively.
In fact, you could take a deck of playing cards (or cards with numbers)
and do this manually.  Here's how this function works, and how a binary
search works:

\begin{enumerate}
\item Set a high and low mark based on the size of the array.
\item Get the middle element between the low and high marks.
\item If the key is less-than, then the key must be below the middle.  Set high to one less than middle.
\item If the key is greater-than, then the key must be above the middle.  Set the low mark one greater than the middle.
\item If it's equal then you found it, stop.
\item Keep looping until low and high pass each other.  You don't find it if you exit the loop.
\end{enumerate}

What you are effectively doing is guessing where the key might be by picking
the middle and comparing it.  Since the data is sorted, you know that the
the key has to be above or below this.  If it's below, then you just divided
the search space in half.  You keep going until you either find it or you
overlap the boundaries and exhaust the search space.

\subsection{RadixMap\_sort And radix\_sort}

A radix sort is easy to understand if you try to do it manually first.  What
this algorithm does is exploit the fact that numbers are stored with a 
sequence of digits that go from "least significant" to "most significant".
It then takes the numbers and buckets them by the digit, and when it has
processed all the digits the numbers come out sorted.  At first it
seems like magic, and honestly looking at the code sure seems like it is,
but try doing it manually once.

To do this algorithm write out a bunch of three digit numbers, in a random
order, let's say we do 223, 912, 275, 100, 633, 120, and 380.

\begin{enumerate}
\item Place the number in buckets by their 1's digit:
    \verb|[380, 100, 120], [912], [633, 223], [275]|.
\item I now have to go through each of these buckets in order, and then sort it into 10's buckets:
    \verb|[100], [912], [120, 223], [633], [275], [380]|.
\item Now each bucket contains numbers that are sorted by the 1's then 10's digit.  I need to then go through these in order and fill the final 100's buckets: 
    \verb|[100, 120], [223, 275], [380], [633], [912]|.
\item At this point each bucket is sorted by 100's, 10's, then 1's and if I
    take each bucket in order I get the final sorted list: 
    \verb|100, 120, 223, 275, 380, 633, 912|.
\end{enumerate}

Make sure you do this a few times so you understand how it works.  It really is
a slick little algorithm and most importantly it will work on numbers of
arbitrary size, so you can sort really huge numbers because you are just doing
them one byte at a time.

In my situation the "digits" are individual 8 bit bytes, so I need 256 buckets
to store the distribution of the numbers by their digits.  I also need a way
to store them such that I don't use too much space.  If you look at
\ident{radix\_sort} first thing I do is build a \ident{count} histogram so I
know how many occurances of each digit there are for the given \ident{offset}.

Once I know the counts for each digit (all 256 of them) I can then use that
as distribution points into a target array.  For example, if I have 10 bytes
that are 0x00, then I know I can place them in the first 10 slots of the
target array.  This gives me an index for where they go in the target
array, which is the second for-loop in \ident{radix\_sort}.

Finally, once I know where they can go in the target array, I simply go 
through all the digits in the \ident{source} array, for this \ident{offset}
and place the numbers in their slots in order.  Using the \ident{ByteOf}
macro helps keep the code clean since there's a bit of pointer hackery
to make it work, but the end result is all of the integers will be
placed in the bucket for their digit when the final for-loop is done.

What becomes interesting is then how I use this in \ident{RadixMap\_sort}
to sort these 64 bit integers by just the first 32 bits.  Remember how
I have the key and value in a union for the \ident{RMElement} type?
That means to sort this array by the key I only need to sort the first
4 bytes (32 bits / 8 bits per byte) of every integer.

If you look at the \ident{RadixMap\_sort} you see that I grab a quick
pointer to the \ident{contents} and \ident{temp} to for source and 
target arrays, and then I call \ident{radix\_sort} four times.  Each
time I call it, I alternate source and target and do the next byte.
When I'm done, the \ident{radix\_sort} has done its job and the final
copy has been done into the \ident{contents}.

\section{How To Improve It}

There is a big disadvantage to this implementation because it has to
process the entire array four times on every insertion.  It does do
it fast, but it'd be better if you could limit the amount of sorting
by the size of what needs to be sorted.

There's two ways you can improve this implementation:

\begin{enumerate}
\item Use a binary search to find the minimum position for the 
    new element, then only sort from there to the end.  You find the
    minimum, put the new element on the end, then just sort from
    the minimum on.   This will cut your sort space down 
    considerably most of the time.
\item Keep track of the biggest key currently being used, and then only
    sort enough digits to handle that key.  You can also keep track
    of the smallest number, and then only sort the digits necessary
    for the range.  To do this you'll have to start caring about
    CPU integer ordering (endianess).
\end{enumerate}

Try these optimizations, but after you augment the unit test with some
timing information so you can see if you're actually improving the
speed of the implementation.

\section{Extra Credit}

\begin{enumerate}
\item Implement quicksort, heapsort, and mergesort and provide a \ident{\#define}
    that lets you pick between the two, or create a second set of functions 
    you can call.  Use the technique I taught you to read the Wikipedia page
    for the algorithm and then implement it with the psuedo-code.
\item Compare the performance of your implementations to the original ones.
\item Use these sorting functions to create a \ident{DArray\_sort\_add} that
    adds elements to the \ident{DArray} but sorts the array after.
\item Write a \ident{DArray\_find} that uses the binary search algorithm from 
    \ident{RadixMap\_find} and the \ident{DArray\_compare} to find elements
    in a sorted \ident{DArray}.
\end{enumerate}