Article Preview
Buy Now
COLUMN
Sorting
Ascending Order in the Court
Issue: 1.2 (October/November 2002)
Author: Matt Neuburg
Author Bio: Matt Neuburg is the author of
Article Description: No description available.
Article Length (in bytes): 10,863
Starting Page Number: 34
Article Number: 1116
Resource File(s):
1116.zip Updated: 2013-03-11 19:07:56
Related Link(s): None
Excerpt of article text...
Probably no algorithms have been the subject of more interest than those used in sorting. Entire books have been written, and entire courses have been taught, on sorting alone. And it's easy to see why. Rearrangement of data is a common need. For one thing, you might like to present ordered data to your user. Also, ordered data is much faster for your program to search, that is, to see whether a given item is present, and if so, where. To find an item in unordered data requires examining every item; to find an item in ordered data requires merely going to the spot where it should be, and this can be very fast, as in the binary search example on p. 57 of my book,
REALbasic: The Definitive Guide .One reason sorting is interesting is that it so heavily taxes the computer's resources. For example, with the need for sorting comes the need for speed. Intuitively one senses that sorting will take more time the more data one has; if this time increase is linear (twice as much data takes twice as long to sort), it becomes prohibitive to sort large data sets at all. There is also a space problem. Suppose there's lots of data. It might all fit in the computer's memory, but what if our sorting method requires making a copy, which won't? Or it might not all fit in the computer's memory to start with; what then?
Much ingenuity has been devoted to solving these problems, and their mathematics are an important aspect of computer science. Luckily, there are now enough sorting "recipes" to satisfy the needs of most beginners. The simplest sorting algorithm is the "bubble sort." It's also one of the worst, so you wouldn't normally use it! Nevertheless, it's worth starting with, just because it's easy to understand and easy to code.
The idea of a bubble sort is that your data is divided into two clumps: the clump you've already sorted, followed by the clump you haven't. You then take the first item of data from the unsorted clump and put it into place in the sorted clump by swapping it with the preceding item as many times as necessary. With each swap, the item moves upwards towards its proper place in the sorted clump; hence the "bubble" metaphor. Here's how the procedure goes:
Start with the first item of data. It's obviously in order relative to itself, so leave it alone. The first item is now sorted.
...End of Excerpt. Please purchase the magazine to read the full article.