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: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
From: miker3@ix.netcom.com (Mike Rubenstein)
Subject: Re: What's the best language to start with? [was: Re: Should I learn
 C or Pascal?]
Date: 1996/08/10
Message-ID: <320bf503.8426726@nntp.ix.netcom.com>#1/1
X-Deja-AN: 173285429
references: <4uaqqg$203@mulga.cs.mu.OZ.AU>
 <01bb84b4$75304ce0$87ee6fce@timpent.airshields.com>
 <4ubnhr$714@news1.mnsinc.com>
 <01bb8536$892ee260$87ee6fce@timpent.airshields.com>
 <4ud8m5$ka5@news1.mnsinc.com>
organization: Netcom
x-netcom-date: Fri Aug 09  7:43:11 PM PDT 1996
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-09T19:43:11-07:00
List-Id: <comp.lang.ada>


huang@mnsinc.com (Szu-Wen Huang) wrote:

> Tim Behrendsen (tim@airshields.com) wrote:
> : Szu-Wen Huang <huang@mnsinc.com> wrote in article
> : <4ubnhr$714@news1.mnsinc.com>...
> 
> : > 1.  Being able to write algorithm X in assembly doesn't make you
> : >     understand the algorithm better.  It makes you understand whatever
> : >     platform du jour your school uses better.
> : > 2.  Vaguely understanding 5 algorithms is far better than understanding
> : >     one or two fully.  The primary objective of algorithms courses is
> : >     to produce students that can *choose* which algorithm to use,
> : >     not to produce students who can memorize one or two algorithms.
> : >     In fact, there's rarely a programmer more dangerous than one that
> : >     has no broad knowledge of algorithms.
> 
> : My point is someone who has "vaguely" learned five algorithms has
> : simply memorized them, and learned nothing about the general
> : principles of how algorithms are created.
> 
> No, your point was writing an algorithm in assembly helps to understand
> it fully.  I'll be my own case in point.  I remember most sorting
> algorithms vaguely, and I probably could not implement all of them
> off the top of my head.  Does that hamper me?  No, because I know
> which book to look them up in, and that's exactly what books are for.
> The important thing, however, is that I remember that O(n^2) is bad
> for a sorting algorithm, and O(n lg n) is pretty good.

But that is not always true.

A number of years ago I developed a program that had to do a large
number of sorts with the following characteristics:

	1.  The mean number of items to be sorted was about 5.  In a 
	    test sample of a million cases, the larges number of items
	    to be sorted was 35.

	2.  The items were usually in order.  In the test sample, 90% 
	    were in order, and most of the rest were in order except 
	    for a single interchange of adjacent items.  Only 8 were 
	    out of order by more than three interchanges or required 
	    interchanges of nonadjacent items.

Care to try this with quicksort?  or heapsort?  A good old O(n^2)
insertion sort works quite nicely.


Michael M Rubenstein