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=-0.8 required=5.0 tests=BAYES_00,INVALID_MSGID,
	URI_NOVOWEL autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,7bb5fdff3abecabe
X-Google-Attributes: gid103376,public
X-Google-Thread: 108717,7bb5fdff3abecabe
X-Google-Attributes: gid108717,public
From: rav@goanna.cs.rmit.edu.au (robin)
Subject: Re: Algorithms: Counting- and AddressCalculation Sort
Date: 1997/11/05
Message-ID: <63ob0t$qv6$1@goanna.cs.rmit.edu.au>#1/1
X-Deja-AN: 287106099
Expires: 1 February 1998 00:00:00 GMT
References: <34509356.32EB39DD@biosys.net> <62qfri$l6h@top.mitre.org>
Organization: Comp Sci, RMIT University, Melbourne, Australia.
NNTP-Posting-User: rav
Newsgroups: comp.programming,comp.lang.ada
Date: 1997-11-05T00:00:00+00:00
List-Id: <comp.lang.ada>


	mfb@mbunix.mitre.org (Michael F Brenner) writes:

	>According to the ieee dictionary at the url: 
	>http://stdsbbs.ieee.org/groups/610/formata.html
	>an address calculation sort is an insertion sort
	>where the items get put into lists based on their
	>addresses and then those lists are merged. That makes
	>it sound like a hashcode is computed and the hashcode
	>is used to determine approximately where to put the
	>item (that is, plus or minus one list). A large enough
	>hashcode, combined with a widely enough distributed
	>statistical distribution of the data, and sufficient
	>RAM (double the key space) results in a very efficient
	>sort. If any of these three is missing, it wont work.
	>If you actually use addresses instead of hash codes, 
	>then double the key space is insufficient. You must
	>have a perfect hashcode address function to linearize
	>the sorting time. Also you must take into account that
	>if you have an imperfect address computation or hashcode,
	>then those lists will have more than one member and 
	>storage space must be made for those lists as well as
	>for links between those lists, and time for maintaining,
	>allocating, and deallocating those lists and their
	>members.

	>According to the URL http://ww.cs.cmu.edu/~scandal/nesl/algorithsm.html
	>a counting sort computes the number of keys less than each of the
	>keys. This does not seem to be a fast way to sort. It also seems
	>that after you have made all of your counts, you must still
	>sort those counts. 

No, if you know for a given item what its count is (i.e., the
number of items that are less than it), then you know its
position in the (sorted) list.  Thus, yu can put it
in its correct position in an array.

e.g., if there are 7 items less than a given item,
then the item is placed in the 8th slot (simple indexing).