Sorting algorithms/Counting sort: Difference between revisions
Content added Content deleted
m (2^32 = 4Gbytes, not 16.) |
(Added Oz.) |
||
Line 472: | Line 472: | ||
sorted = counting_sort(ages, 0, 140); |
sorted = counting_sort(ages, 0, 140); |
||
disp(sorted);</lang> |
disp(sorted);</lang> |
||
=={{header|Oz}}== |
|||
Using arrays as in the original algorithm. The implementation is slightly simpler because arrays can start with an arbitrary index in Oz. |
|||
<lang oz>declare |
|||
proc {CountingSort Arr Min Max} |
|||
Count = {Array.new Min Max 0} |
|||
Z = {NewCell {Array.low Arr}} |
|||
in |
|||
%% fill frequency array |
|||
for J in {Array.low Arr}..{Array.high Arr} do |
|||
Number = Arr.J |
|||
in |
|||
Count.Number := Count.Number + 1 |
|||
end |
|||
%% recreate array from frequencies |
|||
for I in Min..Max do |
|||
for C in 1..Count.I do |
|||
Arr.(@Z) := I |
|||
Z := @Z + 1 |
|||
end |
|||
end |
|||
end |
|||
A = {Tuple.toArray unit(3 1 4 1 5 9 2 6 5)} |
|||
in |
|||
{CountingSort A 1 9} |
|||
{Show {Array.toRecord unit A}}</lang> |
|||
Using lists for input and output and a dictionary as a sparse array: |
|||
<lang oz>declare |
|||
fun {CountingSort Xs} |
|||
Count = {Dictionary.new} |
|||
in |
|||
for X in Xs do |
|||
Count.X := {CondSelect Count X 0} + 1 |
|||
end |
|||
{Concat {Map {Dictionary.entries Count} Repeat}} |
|||
end |
|||
fun {Repeat Val#Count} |
|||
if Count == 0 then nil |
|||
else Val|{Repeat Val#Count-1} |
|||
end |
|||
end |
|||
fun {Concat Xs} |
|||
{FoldR Xs Append nil} |
|||
end |
|||
in |
|||
{Show {CountingSort [3 1 4 1 5 9 2 6 5]}}</lang> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |