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.
Comments