Article Preview
Buy Now
| Print: | |
| PDF: |
Algorithms
Quicksort
Part I
Issue: 5.4 (May/June 2007)
Author: Charles Yeomans
Article Description: No description available.
Article Length (in bytes): 11,101
Starting Page Number: 42
RBD Number: 5416
Resource File(s): None
Related Web Link(s):
http://www.declareSub.com/
Known Limitations: None
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.
Sub Swap(theList() as Integer, index1 as Integer, index2 as Integer)
...End of Excerpt. Please purchase the magazine to read the full article.
Article copyrighted by REALbasic Developer magazine. All rights reserved.
|
