-----Original Message----- From: James Stark [mailto:james_stark03@hotmail.com]
I can confrim that this algorithm does not work - its crap.
You've lost me here. Are you saying that the quicksort algorithm is invalid? Quicksort has been demonstrated to be an excellent sorting algorithm since it was first published back in, what, the early '60's sometime? If you've found a problem with it which has not been adequately discussed in the literature over the past forty years you should certainly write it up - I imagine that any of the reputable journals would be eager to publish your results following peer review. I'm sure that such a formal analysis would be of great interest to many people. I ran some tests on the code you posted and for random arrays with up to 1 million elements the sort was correct. What problem have you discovered?
It starts from the middle? thats not how quicksort is meant to work, its meant to start from the sides (left and right) and when they cross over it meant to assign the pivot value. Actually its meant to assign the pivot value to the left to start off with.
If memory serves you can choose any element as the pivot. Some choices may be better than others. Isn't choosing the left-most element as the initial pivot likely to make the run time O(N^2) if your data is already sorted or nearly so? Similar problem with choosing the right-most if the data is sorted in descending order.
If any of you guys have developed any other algortihms it would be interesting to do a trace. Like a binary tree sort (is that more efficient?) I dont know... just traced that one - made no sense.
What is it that made no sense?
Bob Jarvis Compuware @ Timken
********************************************************************** This message and any attachments are intended for the individual or entity named above. If you are not the intended recipient, please do not read, copy, use or disclose this communication to others; also please notify the sender by replying to this message, and then delete it from your system.
The Timken Company **********************************************************************
On Tuesday, December 4, 2001, at 11:06 AM, Jarvis, Robert P. (Contingent) wrote:
-----Original Message----- From: James Stark [mailto:james_stark03@hotmail.com]
I can confrim that this algorithm does not work - its crap.
You've lost me here.
Just out of curiosity, why are we having this discussion at all? What bearing does it have on Squeak?
squeak-dev@lists.squeakfoundation.org