* Algorithms: Counting- and AddressCalculation Sort @ 1997-10-24 0:00 SiNiStEr 1997-10-24 0:00 ` Michael F Brenner 0 siblings, 1 reply; 3+ messages in thread From: SiNiStEr @ 1997-10-24 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Algorithms: Counting- and AddressCalculation Sort 1997-10-24 0:00 Algorithms: Counting- and AddressCalculation Sort SiNiStEr @ 1997-10-24 0:00 ` Michael F Brenner 1997-11-05 0:00 ` robin 0 siblings, 1 reply; 3+ messages in thread From: Michael F Brenner @ 1997-10-24 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Algorithms: Counting- and AddressCalculation Sort 1997-10-24 0:00 ` Michael F Brenner @ 1997-11-05 0:00 ` robin 0 siblings, 0 replies; 3+ messages in thread From: robin @ 1997-11-05 0:00 UTC (permalink / raw) 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). ^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~1997-11-05 0:00 UTC | newest] Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1997-10-24 0:00 Algorithms: Counting- and AddressCalculation Sort SiNiStEr 1997-10-24 0:00 ` Michael F Brenner 1997-11-05 0:00 ` robin
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox