Re: hc11 program help

From: Max (mtj2_at_btopenworld.com)
Date: 03/01/04 

Date: Mon, 1 Mar 2004 15:37:09 +0000 (UTC)

On Sun, 29 Feb 2004 21:53:12 GMT, Anthony Fremont wrote:

>Interesting. I've seen websites that do indeed suport this claim. I
>saw reference to it for the first time in a Byte magazine article.
>As indicated here: http://world.std.com/~jdveale/combsort.htm and here
>http://en.wikipedia.org/wiki/Comb_sort

Hmmm. The authors of those Wikipedia pages don't seem to acknowledge
the existence of "diminishing-interval sorting" as a class at all.
Odd.

>Shell is not referenced as having anything to do with its authorship at
>all.

Some historical stuff at NIST:
http://www.nist.gov/dads/HTML/shellsort.html

>Credit seems to go to Stephen Lacey and Richard Box.

I don't know - these young un's don't seem to realise there wuz
computers around well before they were born ;o)

>It would
>appear that when refering to an insertion sort of decreasing comparison
>intervals, one should say Shell sort. However, when referring to a
>bubble sort with similar (same?) technique applied, it's a comb sort.

NIST say that comb sort is just another name for the diminishing
interval sort, and credit Shell as the inventor:
http://www.nist.gov/dads/HTML/diminishingIncSort.html

Personally, I regard the comb sort as just a Shell sort with a
different gap factor, and therefore a modification of an existing
algorithm. It's a worthwhile improvement, but Shell should still be
credited for the original invention.

In fact, it's a little hard to tell what is actually supposed to be
original in this Lacey/Box algorithm, given that Knuth evaluated
diminishing-interval with varying gap factors in his standard text on
the subject, the second edition of which came out three years before
the Byte article (and the first edition is circa 1980!). So, I'm going
to ignore Wikipedia, and give the credit for comb sort to Shell and
Knuth. 

-- 
  Max

Relevant Pages

  • Re: How to make Forth interesting?
    ... Shell utilities: ... to do a table indexed with the words: wordlists. ... I guess that there are also systems that include a sort, ... sorting with counted uniqueness is good enough. ...
    (comp.lang.forth)
  • Re: sort + head = weirdness?
    ... >'sort'and then through 'head' and I'm getting really strange results. ... >works fine with 'sort' itself. ... buffer, so there's no attempt to write anything after "head" has exited. ... Check the documentation of the shell (you didn't say what shell you're ...
    (comp.unix.shell)
  • Re: Which countries contribute most to the total?
    ... If you're going to use UNIX sort and forget about skipping the header ... or various other options that just has shell call awk rather than ...
    (comp.lang.awk)
  • Re: Sort files by filename
    ... expansions in sorted order. ... the shell has already generated the list. ... You have more options on how you sort by piping ...
    (Fedora)
  • Re: how do i change the default sort of the media player
    ... Sort order in the shell doesn't matter at all. ... then right click and select play. ...
    (microsoft.public.windowsmedia.player)