🚀 go-pugleaf

Kristof Roomp (krisr@cue.bc.ca) wrote:
: In article <1992Nov8.012628.23338@menudo.uh.edu> libh@Jane.UH.EDU writes:
: >  The bubble sort takes N! (# factorial) steps, rather than N*N steps.  A BIG
: >difference.  But as pointed out, the quicksort is the easiest to implement
: >since it is in C libraries.  Why reinvent the wheel.  If that isn't quick
: >enough then I would check out Knuth's 'Art of Programming' Vol. 3 since it is
: >pretty much only about sorting.
: >
: nope.its worst case is n*n where n is the number of items in the list...
: you have to watch the quicksort with lists of objects which are already
: sorted, because its performance on a sorted list is a lot worse than
: the bubble sort. on a presorted list , the quicksort will also use
: in the order of n stack space. This could be prevented by taking a different
: pivot element when quicksorting (like the middle one). the library quicksort
: uses the first element.
: 
Some time back, I and a friend of mine were competing on who could write the
fastest sort routine. The fastest result was combining the bubble and the
quick sort routines, like using the bubble to determine the threshold as well
as checking wether the data already was sorted or not. This way, the routine
would have only one pass if the list already was sorted.

I COULD see if I can find the routine, if I look in my archived routines
library. I have one written for Power BASIC (on the Atari ST series computers)
and another one written in pure 68000 assembler.

/Gard