Special

Introducing the “Welcome to Xojo” Bundle!

New to Xojo and looking for guidance? We've put together a terrific bundle to welcome you! Xojo Bundle

This bundle includes six back issues of the magazine -- all of year 21 in printed book and digital formats -- plus a one-year subscription (beginning with 22.1) so you'll be learning all about Xojo for the next year. It's the perfect way to get started programming with Xojo. And you save as much as $35 over the non-bundle price!

This offer is only available for a limited time as supplies are limited, so hurry today and order this special bundle before the offer goes away!

Article Preview


Buy Now

Issue 1.2

COLUMN

Sorting

Ascending Order in the Court

Issue: 1.2 (October/November 2002)
Author: Matt Neuburg
Author Bio: Matt Neuburg is the author of REALbasic: The Definitive Guide, and a member of the editorial board of REALbasic Developer.
Article Description: No description available.
Article Length (in bytes): 10,863
Starting Page Number: 34
Article Number: 1116
Resource File(s):

Download Icon 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.