Article Preview
Buy Now
| Print: | |
| PDF: |
Algorithms
Quicksort
Part II
Issue: 5.5 (July/August 2007)
Author: Charles Yeomans
Article Description: No description available.
Article Length (in bytes): 10,287
Starting Page Number: 42
RBD Number: 5515
Resource File(s): None
Related Web Link(s):
http://www.declareSub.com/
Known Limitations: None
Excerpt of article text...
In the previous installment of this column, I worked through the basic version of the quicksort algorithm. It is this: given an array, pick an element, and call it the pivot. Move all elements of the array less than the pivot to the left, and all elements of the array greater than the pivot to the right. Afterward, the pivot element is in its sorted position. Now repeat this process on the two subarrays to the left and the right of the pivot.
I also discussed some optimization of this algorithm in the course of implementing it; I recall the code here.
Sub QuickSort(theList() as Integer, firstIndex as Integer, lastIndex as Integer)
#pragma disableBackgroundTasks
if lastIndex - firstIndex < 10 then
InsertionSort theList, firstIndex, lastIndex
return
end if
if theList(firstIndex) > theList(lastIndex) then
dim tmp as Integer = theList(firstIndex)
theList(firstIndex) = theList(lastIndex)
theList(lastIndex) = tmp
end if
dim pivot as Integer = theList(firstIndex)
...End of Excerpt. Please purchase the magazine to read the full article.
Article copyrighted by REALbasic Developer magazine. All rights reserved.
|
