Anonymous user
Sorting algorithms/Counting sort: Difference between revisions
m
made the last sentence in the task's prologue to be a counterexample for the note.
m (→{{header|REXX}}: changed the separator line.) |
m (made the last sentence in the task's prologue to be a counterexample for the note.) |
||
Line 6:
;Task:
Implement the [[wp:Counting sort|Counting sort]]. This is a way of sorting integers when the minimum and maximum value are known.
;Pseudocode:
'''function''' ''countingSort''(array, min, max):
count: '''array of''' (max - min + 1) '''elements'''
Line 28:
'''Note''': we know that, given an array of integers, its maximum and minimum values can be always found; but if we imagine the worst case for an array that can hold up to 32 bit integers, we see that in order to hold the counts, an array of up to '''2<sup>32</sup>''' elements may be needed. I.E.: we need to hold a count value up to '''2<sup>32</sup>-1''', which is a little over 4.2 Gbytes. So the counting sort is more practical when the range is (very) limited, and minimum and maximum values are known ''a priori''. (
<br><br>
| |||