Introduction
Are you feeling out-of-sorts these days? Do you want order in your life? Do you
believe that A is less than B? Then you need to know how to sort!
Sorting is, on the whole, a complex task. Don Knuth devotes one entire volume
of his famous "Art of Computer Programming" entirely to this topic, "Sorting
and Searching". If you want the real truth, go read that. There are also
many other books written on the topic.
Old Faithful: the Bubble Sort
If you have a very tiny number of objects to sort, you can use an algorithm
called "bubble sort". It gets its name from the fact that elements "bubble" up
to the end of the array, until the array is sorted.
The Good News: this is the easiest sort to write.
The Bad News: it is a really,
really bad way to sort. (It is not the worst possible sort, but it is definitely
in the running).
The problem with bubble sort is that it is, in the worst case, an "order
n2 sort", that is, if it takes time T to sort k elements, then it will
take time 100T to sort 10k elements. And 10,000T to sort 100k elements.As n
goes up, the time goes up as n2. But if you've only got five or ten items to
sort, it works
fine.template <class T> void bubble(T data[],
UINT count)
{
BOOL changed = TRUE;
while(changed)
{ /* scan */
changed = FALSE;
for(UINT i = 0; i < count - 1; i++)
{ /* compare */
if(data[i+1] < data[i])
{ /* swap */
T t = data[i];
data[i] = data[i + 1];
data[i+1] = t;
changed = TRUE;
} /* swap */
} /* compare */
} /* scan */
} // bubble
The worst
possible sort was invented by Dr. Guy L. Steele, Jr. He calls it "bogo-sort" and
it is intended to represent the worst sorting algorithm he could imagine.
Do you know the game called "52 pickup"? You fill in the array
in random order. You then check to see if it is in sorted order. If it
is, you are done. If it isn't, you repeat the algorithm. You keep this
up until you discover that the array is fully sorted.
The game of "52 pickup" is
usually played with a small child. "Here's 52 cards", you say,
holding the deck up. "Do you want to play 52 pickup?" The child,
unless he or she has seen this before, says "Sure!". You toss
all the cards on the floor. "That's the game. You pick them
up". Now imagine that all the cards are face-down. Bogo-sort requires
that when you assemble the cards, they are all in order by value and suit.
If not, you play 52 pickup again. In bogo-sort, you are not permitted to
look at the faces of the cards while picking them up.