Article Preview
Buy Now
| PDF: |
Algorithms
Sorting, Part 2
Heaps of Fun
Issue: 1.3 (December/January 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,451
Starting Page Number: 34
RBD Number: 1317
Resource File(s):
1317.sit Updated: Friday, October 17, 2003 at 12:20 PM
Related Link(s): None
Known Limitations: None
Excerpt of article text...
Cast your mind back to the last issue of REALbasic Developer, when this column described Bubblesort, an easily understood but prohibitively slow sorting algorithm. We also saw that, when the items to be sorted are objects, it makes sense to embed in the items themselves the knowledge of how their relative ordering works. For maximum generality, we had our objects implement the ComparableThing class interface, so that we could then send any object the ShouldSwapWith message, along with some other object as parameter, to learn whether the first object is, on its own terms, "less than" the second.
In this issue's column we'll develop a better sorting algorithm. You might expect, if you're familiar with these matters, that this would be the popular Quicksort; but instead I've elected to talk about Heapsort. There are two reasons for this choice. First, Quicksort, though faster than Heapsort in the best cases, is complicated to implement in a way that is always fast; in fact, in the worst case it can be as slow as Bubblesort, while Heapsort's speed remains consistent. Also, Heapsort depends upon a secondary notion, the heap, which is intriguing in its own right. (Another interesting sorting algorithm, Shell sort, is shown on p. 162 of REALbasic: The Definitive Guide.)
...End of Excerpt. Please purchase the magazine to read the full article.
Article copyrighted by REALbasic Developer magazine. All rights reserved.
|
