When I run across a particularly fast elegant algorithm I often find myself asking, “Why it is fast?” How can I make my algorithms fast like the author of this one did? I have found that the answer usually is found in how the algorithm manages data. How does the algorithm preserve work and prevent recalculating information? To step back a bit, there are only three ways to make some code go faster, find a way to make what it is doing faster, find a way to do less, find some other time to do it. The most elegant algorithms do the second well; they do less. For a few entries I want to look at various algorithms to see what makes them fast (or not so fast).
The first set of algorithms I want to investigate are some of the most fundamental, sorting. The simplest sort to write is the selection sort. In C# it looks like,
Swap looks like,
This sort finds the smallest item in the list and puts it first, and then it
finds the second smallest and puts it second, etc. Even though it is very easy
to write and relatively easy to verify, it isn’t very fast. We could improve
this by in-lining the
Swap() method. Additionally, we can limit the number of
swaps to a.Length by only swapping the value we know is the smallest. A version
that includes both optimizations is,
These optimizations are examples of making what we are doing faster. Unfortunately, we still with do on the order of O(N2) comparisons even though we reduced the number of moves to O(N) and removed any overhead of doing a call in the middle of the loop. What we really want to do is less. To do less we need to come up with information we are not using or information we are throwing away.
Since we are trying to optimize the number of comparisons (since we got the
moves down to O(N)) we should examine them closely. We need to come up with a
way to make each comparison do more. One thing we should notice is the above
algorithm totally ignores the transitive nature of a compare. That is if A > B
and B > C then A > C. If we know that
a > a and
a > a we
don’t need to physically do the comparison between
a to know
a > a, but how do we take advantage of that? In my next “sorting”
post I will investigate an algorithm that takes advantage of this.