Article Preview

COLUMN

Quicksort

Part I

Issue: 5.4 (May/June 2007)
Author: Charles Yeomans
Author Bio: Charles is the author of I Declare: Calling External Functions in REALbasic, available online at http://www.declareSub.com/
Article Description: No description available.
Article Length (in bytes): 12,350
Starting Page Number: 42
Article Number: 5416
Related Web Link(s):

http://www.declareSub.com/

Excerpt of article text...

In this issue's column we tackle Quicksort. Quicksort is perhaps the most widely-used sorting algorithm, because it is very fast and suited to general application. It is the most widely-studied algorithm because it is not always very fast, and its performance is quite sensitive to changes in its implementation, thus encouraging endless tinkering.

The basic idea is simple. Given a list, we first partition it. Pick one element, and call it the pivot. Then compare each element of the array to the pivot, placing elements less than the pivot to one side, and elements greater than the pivot to the other. We now know the position of the pivot element in the sorted list; it lies between the two subsets. Now apply the same algorithm to each of the two subsets. As we'll see, the success of Quicksort depends mostly on getting the partition right, and this is not so easy.

For convenience, we first write a simple method that swaps two elements of an array.

...End of Excerpt. Please purchase the magazine to read the full article.