From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
From: heller@utdallas.edu (Steve Heller)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/16
Message-ID: <4v2fb9$lpj@news.utdallas.edu>#1/1
X-Deja-AN: 174592188
references: <31FBC584.4188@ivic.qc.ca>
 <01bb83f5$923391e0$87ee6fce@timpent.airshields.com>
 <4uah1k$b2o@solutions.solon.com>
 <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com>
 <4udb2o$7io@solutions.solon.com> <EACHUS.96Aug8155946@spectre.mitre.org>
 <4umeot$re2@hil-news-svc-2.compuserve.com> <dewar.839831192@schonberg>
organization: The University of Texas at Dallas
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-16T00:00:00+00:00
List-Id: <comp.lang.ada>


dewar@cs.nyu.edu (Robert Dewar) wrote:

>Radix sorts are not O(n), the analysis is not that simple. They are
>O(kN) where k is the number of radix digits in the numbers, 
  As I understand it, the O() notation indicates how the time to
process varies with the number of elements. E.g., if 1000 elements
take 1 second and 2000 elements take 2 seconds to sort, the sorting
algorithm is O(n). According to this definition, the distribution
counting sort is O(n).

>and if you use left to right (e.g. radix exchange sorting), the early
>termination for subsets of 1 results in an ONlogN behavior after all.
  I generally use right to left, as it is easier to explain. Also, I
don't recall if the left to right version is stable; I know right to
left is.

>Still it is quite true that a simple radix sort for cards will beat
>the heap and quicksort crowds :-)
  Yes.

>I agree that both radix sorts and address calculation sorts should be
>taught more systematically. The reason that attention tends to focus
>on comparison sorts is that these analyze most nicely from an academic
>point of view :-)
  They're more complex to analyze; is that what you mean?

Steve Heller, author and software engineer
http://ourworld.compuserve.com/homepages/steve_heller