Laurence Reeves writes:
In reply to Per's comments earlier, as Norman in effect says, quicksort
is *not* a good all-rounder.
and
The raw figures are at http://www.bergbland.info/2secs.txt and here.
Your figures seem to be saying the opposite of what you write!
And what is the problem
Tony Firshman wrote:
Incidentally Pipex puts the page in a frame.
No they didn't. 11 did that. I've never worked out exactly why they do
that.
The *real* url is http://www.auni40.dsl.pipex.com/sime.html
No Tony... the *real* URL is as I gave it. When I again move the files,
as I have
[EMAIL PROTECTED] wrote:
[EMAIL PROTECTED] wrote:
SNIP
OK. So the random order - quicksort marginally outperforms heapsort. For
the already sorted case, quicksort is rather better than heapsort, but
its margin goes down as the count goes up. However, with the data all
the same...
Dilwyn Jones wrote:
The second one is much faster than the first.
They both use O(n) stack space. The both have O(n*n) worst cases. They
both use the first element as the mean, so will have O(n*n) when the
data is initially sorted. I'd not use either.
Timing checks I did on
it some time ago
Having cured the many bugs in my simple implementations, I now have a
slightly more conventional set of results:
The raw figures are at http://www.bergbland.info/2secs.txt and here.
A spreadsheet... get http://www.bergbland.info/2secs.ods.
The first section is the test code running with calls
[EMAIL PROTECTED] wrote:
SNIP
OK. So the random order - quicksort marginally outperforms heapsort. For
the already sorted case, quicksort is rather better than heapsort, but
its margin goes down as the count goes up. However, with the data all
the same... ooopppsss my quicksort has
Very quick response... you have the normal HUGE bug. When you split
the
array into a left and right chunk, you MUST stack the LARGER chunk,
and
sort the smaller one. That's why the stack space disappears.
And... be very careful about what happens when you can have
duplicate
values...
Laurence Reeves writes:
P Witte wrote:
Laurence Reeves writes:
P Witte wrote:
Quicksort is so much faster than any stable sort I know
of, even when cheating, that its worth it ;o)
Yeah, yeah. I, of course, agree totally. I cheat /all/ the time.
Cheats I dont easily agree with are those
Dilwyn Jones writes:
So here's my attempt at a non-recursive version which probably defeats
the object (apart from not making QLiberator fall over with the stack
space demands).
I got this working some time ago, apart from not being able to make it
handle subscript 0 of the array being
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
Laurence Reeves wrote:
Tony Firshman wrote:
My incorrect re-def of sime; snipped - shorry)
Curiously... I tried to upload an example of sime; on a MathML page to
my website. I don't quite understand this, but Pipex will let me
up/download
P Witte wrote:
Laurence Reeves writes:
P Witte wrote:
Quicksort is so much faster than any stable sort I know
of, even when cheating, that its worth it ;o)
Yeah, yeah. I, of course, agree totally. I cheat /all/ the time.
Cheats I dont easily agree with are those
P Witte wrote:
Quicksort is so much faster than any stable sort I know
of, even when cheating, that its worth it ;o)
Yeah, yeah. I, of course, agree totally. I cheat /all/ the time.
I did get a bit carried away... and perused the current net thinking on
sort algorithms, and it would seem
Dilwyn Jones writes:
Many of you will be familiar with the Quicksort recursive sorting
routine. I wanted to sort large amounts of data at one stage and
compiled a program containing a recursive routine, which quickly ran
out of stack space for all the recursion it needed.
Im just in the
P Witte wrote:
IIRC the resulting sort is stable allowing for an unambiguous fast binary
search (also included) of the array(s) using the same criteria as for the
sort. (That was at least my programming goal. I'll have to check this,
though.)
Sorry? I don't think I follow your banter. A
14 matches
Mail list logo