Sorting algorithms/Counting sort: Difference between revisions

Content added Content deleted
m (→‎version 1: added/changed whitespace and comments, simplified and optimized a DO loop..)
(Elided the word "anyways" from the last sentence in the task's preamble, strengthened the wording about the use of sparse arrays, also elided a stray comma, cleaned up some wording in the last paragraph, added other wording.)
Line 26:
The ''min'' and ''max'' can be computed apart, or be known ''a priori''.
 
 
'''Note''': &nbsp; we know that, given an array of integers, &nbsp; its maximum and minimum values can be always found; &nbsp; but if we imagine the worst case for an array ofthat can hold up to 32 bit integers, &nbsp; we see that in order to hold the counts, we need&nbsp; an array of up to '''2<sup>32</sup>''' elements, imay be needed.e &nbsp; I.,E.: &nbsp; we need, to hold a count value up to '''2<sup>32</sup>-1''', more&nbsp; orwhich lessis a little over 4.2 Gbytes. &nbsp; So the counting sort is more practical when the range is (very) limited, &nbsp; and minimum and maximum values are known &nbsp; ''a priori''. &nbsp; (AnywayThe use of &nbsp; ''sparse arrays'' may&nbsp; limitminimizes the impact of the memory usage, &nbsp; as well as removing the need of having to know the minimum and maximum values &nbsp; ''a priori''.)
<br><br>
 
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort"