peraino@gmu90x.gmu.edu (peraino) (12/05/89)
>Well, insertion sort is only better than bubble sort by a constant factor. >I'll try to write a sort routine that sorts 50 numbers in 30 seconds or so. >This should be possible. (I hope) >Ge' Weijers, ge@cs.kun.nl I don't suppose anyone besides myself grabbed the recursive quicksort that was posted here a while back? ----------------------------------------------------------------------------- Bob Peraino UUCP : uunet!pyrdc!gmu90x!peraino George Mason University INTERNET: peraino@gmuvax.gmu.edu UCIS, Thompson Hall, rm 2 <- BITNET : peraino@gmuvax 4400 University Drive \ PHONE : (703)-323-2549 Fairfax, VA 22030 \- Yeah, they put us in the basement, too. -----------------------------------------------------------------------------
dylan@cs.washington.edu (Dylan McNamee) (12/06/89)
>>Well, insertion sort is only better than bubble sort by a constant factor. >>I'll try to write a sort routine that sorts 50 numbers in 30 seconds or so. >>Ge' Weijers, ge@cs.kun.nl > I don't suppose anyone besides myself grabbed the recursive >quicksort that was posted here a while back? I grabbed the quicksort that was posted here (and is also in the gmu archives) and was very impressed. It outperformed my implementation of mergesort by a factor of 2. (both are O(nlogn) sorts) The only thing wrong with it is that it chooses the first element of the list as the pivot, which puts an already sorted list in its worst case (n^2). All in all, though, it is the most compact sort I've seen, and it is quite fast. dylan dylan@cs.washington.edu
alonzo@microsoft.UUCP (Alonzo Gariepy) (12/09/89)
In article <2423@gmu90x.gmu.edu> peraino@gmu90x.gmu.edu (peraino) writes: > > >Well, insertion sort is only better than bubble sort by a constant factor. > >I'll try to write a sort routine that sorts 50 numbers in 30 seconds or so. > >This should be possible. (I hope) > > I don't suppose anyone besides myself grabbed the recursive > quicksort that was posted here a while back? Running that quicksort on a list of 50 random number (generated with << 1 50 START RAND NEXT 50 ->LIST >>) took 19.5 seconds. Running it a second time on the sorted result took 118 seconds, six times longer. That's quicksort for you. There are ways to minimize this effect as discussed in Sedgewick's "Algorithms", a really good book on all sorts of things. It is considered a good idea to switch to insertion sorting at some point in a quicksort. Knuth gives a good treatment of this calculation on page 120 of "The Art of Computer Programming Vol. 3". Typically, you would use an insertion sort on sublists with less than 10 or 20 elements. Alonzo Gariepy alonzo@microsoft