From: Colin James 0621 <cjames@dsc.blm.gov>
Subject: RE: Hoare's gripes about Ada (should be who so what)
Date: Thu, 2 Sep 93 5:39:32 MDT [thread overview]
Message-ID: <9309020539.aa05156@dsc.blm.gov> (raw)
Peter Juhl at AT&T writes that it is unclear to which big-O statistics
I refer. See Donald Knuth, "The Art of Computer Programming", Volume 3
Sorting / Searching, 1973, p 381. Juhl terms distribution counting as
radix sorting. This is theoretically true, but practically mistaken.
See Robert Sedgwick's "Algorithms", 1983, p 99 ff. Knuth warns that
distribution counting "is very useful when keys have a small range"
(p 379) and that "[r]adix sorting should not be used for small N!"
(p 380).
For those interested in the source code, I have been deluged by requests
but haven't been able to post the C source yet on the Xenix box at work.
urce code (and working implementations in TrueBASIC
which are portable and easy to translate) can be found on CEC Services
BBS at (303) 231 - 9438, use account "tdsdemo" and password "demo". At
the prompt type "fb" to see the files available. To view and capture the
C pseudo code type "v dcntsort.txt". The pseudo code is after Sedgwick's
Pascal pseudo code.
reply other threads:[~1993-09-02 11:39 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox