|
Hmm. I would say this is "the" quicksort method (well, I don't really know, but I'm guessing). I slightly modified an algorithm I found. I did one or two things to make it look nicer (instead of breaking out of a loop with goto) but those things actually add 2 comparisons (the AND in the while loops) in some cases, so they may slow it down a hair. I suppose I could take them out to see if performance increases. Also, if I wanted to lengthen the script a bit, I could add an insertion sort for segments smaller than 12 items to speed it up further.
Back to the question of whether or not it is "the" quicksort method, hmm. Well, according to the documentation I was reading, the recursive method is called quicksort and the iterative is called qsort.... So, I'm not sure if that was a distinction made by just the author or what, but I'll just call it iterative quicksort. I've looked at several different versions of quicksort, and this one seems to be the best I've found that is not recursive.
Naw.. it wouldn't take you that long:
$a - array
$ls - lower index stack
$us - upper index stack
$sp - stack pointer
$L - lower index
$U - upper index
$i - counter moving from lower index to the right
$j - counter moving from upper index to the left
$p - value of pivot
$t - temp variable for swapping elements
$m - stores either lower or upper index of unsorted segment of the array
If you want to understand the algorithm, it works like this:
1. choose a pivot point
2. swap the elements so that all the elements greater than the pivot are on the right, and all the elements less than are on the left. The pivot point will end up in its correct final position.
3. There will be an unsorted array to the left and right of the pivot, so sort the smaller of the two and put the lower and upper bound of the larger array on the stacks.
4. Continue until each segment is sorted, pulling the lower and upper bound of the unsorted segments of the array off the stack in sequence.
......
There are some nuances to the procedure, but this is the general idea.
Brian
| 
