Sorting algorithms/Counting sort: Difference between revisions
Added 11l
MaiconSoft (talk | contribs) m (Added Delphi reference to Pascal code) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 30:
'''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''. (The use of ''sparse arrays'' minimizes the impact of the memory usage, as well as removing the need of having to know the minimum and maximum values ''a priori''.)
<br><br>
=={{header|11l}}==
{{trans|Python}}
<lang 11l>F countingSort(a, min, max)
V cnt = [0] * (max - min + 1)
L(x) a
cnt[x - min]++
[Int] result
L(n) cnt
result [+]= [L.index + min] * n
R result
V data = [9, 7, 10, 2, 9, 7, 4, 3, 10, 2, 7, 10, 2, 1, 3, 8, 7, 3, 9, 5, 8, 5, 1, 6, 3, 7, 5, 4, 6, 9, 9, 6, 6, 10, 2, 4, 5, 2, 8, 2, 2, 5, 2, 9, 3, 3, 5, 7, 8, 4]
print(countingSort(data, min(data), max(data)) == sorted(data))</lang>
{{out}}
<pre>
1B
</pre>
=={{header|360 Assembly}}==
Line 100 ⟶ 121:
-7 0 2 6 11 13 15 15 21 22 26 28 29 32 34 35 39 41 43 44 46 51 53 56 64 70 74 82 89 91 92 92
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
| |||