Date: Fri, 16 Aug 2002 05:02:42 +0000
Reply-To: sashole@bellsouth.net
Sender: "SAS(r) Discussion" <SAS-L@LISTSERV.UGA.EDU>
From: Paul Dorfman <paul_dorfman@HOTMAIL.COM>
Subject: Re: tip Knuth Sorting by Counting
Content-Type: text/plain; format=flowed
From: "David L. Cassell" <Cassell.David@EPAMAIL.EPA.GOV>
>As Ron points out, the counting sort is O(n).
David,
It depends on what kind of counting sort it is. The running time of the
comparison-based counting sort is dominated by the factor N*N, so it is no
better than the insertion or bubble. But it is the distribution counting
sort (based on a different philosophy altogether) that runs in O(N). And as
you go on to note, yes, there is a price to pay. Another name for the
distribution counting, primarily used by Sedgewick, and I think more on ehte
target, is the key-indexed sort. Since it basically does the same thing as
the key-indexed search, it should be no surprise that it runs in O(N) (for
it searches in O(1)) and is limited to integer keys falling in a limited
range!
>The radix sort is too.
Well, since the radix sort is nothing but a k-staged key-indexed sort, there
is no big surprise, either. The really stupendous thing about this sorting
method is that perhaps being the fastest contemporary sorting method lending
itself to the modern computer architecture, the radix is also the oldest
sorting scheme used in the IBM's 1923 Tabulating Machine. Also, the radix
sort never fails to impress a heck out of a sorting novice, for the method
is extremely counterintuitive - it is a least-significant-digit-first (LSD)
sort, yet it does work.
>However, it is not always feasible to use either of
>these, and their use requires knowledge of the data which is not
>available in most cases. One certainly couldn't use them for
>an arbitrary, unknown data set, such as what PROC SORT has to
>be ready for.
That is why comparison-based sorts are still there - they do not care about
the nature of the key - one of the reasons the Quicksort has spread so
widely!
Kind regards,
==================
Paul M. Dorfman
Jacksonville, FL
==================
_________________________________________________________________
Send and receive Hotmail on your mobile device: http://mobile.msn.com
| 
