Algorithms: Counting- and AddressCalculation Sort

Algorithms: Counting- and AddressCalculation Sort

[SiNiStEr]

I'm am doing an asignment on two different sorting methods in
algorithms, counting- and
address calculation sort, and got stuck in the begining. I can't find
anything about these
methods and all the books at school containing the subject are out to
loan. So what I
need is someone to explain the basic theory behind these two sorting
methods.

Thanks
Anders

Re: Algorithms: Counting- and AddressCalculation Sort

[Michael F Brenner]

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. 

Re: Algorithms: Counting- and AddressCalculation Sort

[robin]

	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).