Sorting algorithms/Counting sort: Difference between revisions
→{{header|langur}}
(Added solution for Action!) |
Langurmonkey (talk | contribs) |
||
(18 intermediate revisions by 13 users not shown) | |||
Line 34:
{{trans|Python}}
<
V cnt = [0] * (max - min + 1)
L(x) a
Line 45:
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))</
{{out}}
Line 53:
=={{header|360 Assembly}}==
<
COUNTS CSECT
USING COUNTS,R13 base register
Line 116:
COUNT DC 200F'0' count
REGEQU
END COUNTS </
{{out}}
<pre>
Line 124:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program countSort64.s */
Line 342:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|Action!}}==
<
PROC PrintArray(INT ARRAY a INT size)
Line 408:
Test(c,8,101,108)
Test(d,12,-1,1)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Counting_sort.png Screenshot from Atari 8-bit computer]
Line 434:
=={{header|ActionScript}}==
<
{
var count:Array = new Array(array.length);
Line 449:
}
return array;
}</
=={{header|Ada}}==
<syntaxhighlight lang="ada">
with Ada.Numerics; use Ada.Numerics;
with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;
procedure Counting_Sort is
type Data is array (Integer range <>) of Natural;
procedure Sort(Item : in out Data) is
minValue, maxValue: Natural;
begin
for I in Item
if Item(I) < minValue then minValue := Item(I); end if;
if Item(I) > maxValue then maxValue := Item(I); end if;
end loop;
declare
Count : Data(minValue .. maxValue);
itemPos : Integer range Item'First - 1 .. Item'Last;
begin
for I in Count'Range loop
Count(I) := 0;
end loop;
for I in Item'Range loop
Count(Item(I)) := Count(Item(I)) + 1;
end loop;
itemPos := 0;
for I in Count'Range loop
for J in 1..Count(I) loop
itemPos := itemPos + 1;
Item(itemPos) := I;
end loop;
end loop;
end;
end Sort;
Stuff : Data(1..
Seed : Generator;
begin
Put("Before: ");
for I in Stuff'Range loop
Stuff(I) := Integer( Float'Truncation( Random( seed ) * 100.0 ) );
Put(Natural'Image(Stuff(I)));
end loop;
New_Line;
Sort(Stuff);
Put("After : ");
for I in Stuff'range loop
Put(Natural'Image(Stuff(I)));
end loop;
New_Line;
end Counting_Sort;
</syntaxhighlight>
{{out}}
<pre>
Before: 45 3 47 5 56 24 95 7 40 65 54 19 63 59 77 99 48 24 12 49 57 86 98 99 97 13 74 44 11 4
After : 3 4 5 7 11 12 13 19 24 24 40 44 45 47 48 49 54 56 57 59 63 65 74 77 86 95 97 98 99 99
</pre>
=={{header|ALGOL 68}}==
Line 485 ⟶ 518:
<br>
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
<
(
INT z := LWB array - 1;
Line 524 ⟶ 557:
FOR i TO UPB ages DO print((" ", whole(ages[i],0))) OD;
print(new line)
)</
Sample output:
Line 530 ⟶ 563:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program countSort.s */
Line 734 ⟶ 767:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
=={{header|Arturo}}==
<
a: new items
rng: inc maximum - minimum
Line 757 ⟶ 790:
]
print countingSort [3 1 2 8 5 7 9 4 6] 1 9</
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|ATS}}==
<syntaxhighlight lang="ats">#include "share/atspre_staload.hats"
(* My ATS solution to the radix sort task includes a counting sort for
values in 0..255. Here, I will write an implementation that works
with a given range of keys. *)
(* - - - - - - - - - - - - - - - - - - - - - - *)
(* Interface *)
exception counting_sort_exception of (string)
extern fn {a : t@ype}
{tk : tkind}
counting_sort
{n : int}
{keymin, keymax : int | keymin <= keymax}
(arr : &array (a, n) >> _,
n : size_t n,
keymin : g1int (tk, keymin),
keymax : g1int (tk, keymax))
:<!exn,!wrt> void
extern fn {a : t@ype}
{tk : tkind}
counting_sort$key : a -<> g1int tk
(* - - - - - - - - - - - - - - - - - - - - - - *)
(* Implementation *)
fn {a : t@ype}
{tk : tkind}
count_entries
{n : int}
{keymin, keymax : int | keymin <= keymax}
(arr : &array (a, n),
n : size_t n,
keymin : g1int (tk, keymin),
keymax : g1int (tk, keymax),
bins : &array (size_t, keymax - keymin + 1))
:<!exn,!wrt> void =
$effmask_ntm (* The for-loop obviously terminates. *)
begin
let
prval () = lemma_array_param arr
var i : [i : nat | i <= n] size_t i
in
for (i := i2sz 0; i <> n; i := succ i)
let
val key = counting_sort$key<a> arr[i]
in
if key < keymin then
$raise counting_sort_exception ("key too low")
else if keymax < key then
$raise counting_sort_exception ("key too high")
else
bins[key - keymin] := succ bins[key - keymin]
end
end
end
fn {}
bin_sizes_to_indices
{num_bins : int}
(bins : &array (size_t, num_bins) >> _,
num_bins : size_t num_bins)
:<!wrt> void =
let
fun
loop {i : nat | i <= num_bins}
{accum : int}
.<num_bins - i>.
(bins : &array (size_t, num_bins) >> _,
i : size_t i,
accum : size_t accum)
:<!wrt> void =
if i <> num_bins then
let
prval () = lemma_g1uint_param i
val elem = g1ofg0 bins[i]
in
if elem = i2sz 0 then
loop (bins, succ i, accum)
else
begin
bins[i] := accum;
loop (bins, succ i, accum + elem)
end
end
prval () = lemma_array_param bins
in
loop (bins, i2sz 0, i2sz 0)
end
fn {a : t@ype}
{tk : tkind}
rearrange {n : int}
{keymin, keymax : int | keymin <= keymax}
(arr : &array (a, n) >> _,
temp : &array (a, n),
n : size_t n,
keymin : g1int (tk, keymin),
keymax : g1int (tk, keymax),
bins : &array (size_t, keymax - keymin + 1))
:<!wrt> void =
let
prval () = lemma_array_param arr
fun
loop {i : nat | i <= n}
.<n - i>.
(arr : &array (a, n) >> _,
temp : &array (a, n),
bins : &array (size_t, keymax - keymin + 1),
i : size_t i)
:<!wrt> void =
if i <> n then
let
val key = counting_sort$key<a><tk> temp[i]
val () = $effmask_exn assertloc (keymin <= key)
val () = $effmask_exn assertloc (key <= keymax)
val index = g1ofg0 bins[key - keymin]
prval () = lemma_g1uint_param index
val () = $effmask_exn assertloc (index < n)
val () = arr[index] := temp[i]
val () = bins[key - keymin] := succ index
in
loop (arr, temp, bins, succ i)
end
in
loop (arr, temp, bins, i2sz 0)
end
implement {a} {tk}
counting_sort {n} {keymin, keymax} (arr, n, keymin, keymax) =
if n <> i2sz 0 then
let
stadef num_bins = keymax - keymin + 1
val num_bins : size_t num_bins = succ (g1i2u (keymax - keymin))
val @(pf_bins, pfgc_bins | p_bins) =
array_ptr_alloc<size_t> num_bins
macdef bins = !p_bins
val () = array_initize_elt<size_t> (bins, num_bins, i2sz 0)
val () = count_entries<a><tk> (arr, n, keymin, keymax, bins)
val () = bin_sizes_to_indices<> (bins, num_bins)
val @(pf_temp, pfgc_temp | p_temp) = array_ptr_alloc<a> n
macdef temp = !p_temp
val () = array_copy<a> (temp, arr, n)
val () = rearrange<a><tk> (arr, temp, n, keymin, keymax, bins)
val () = array_ptr_free (pf_temp, pfgc_temp | p_temp)
val () = array_ptr_free (pf_bins, pfgc_bins | p_bins)
in
end
(* - - - - - - - - - - - - - - - - - - - - - - *)
typedef record = [i : int | 1 <= i; i <= 9] '(int i, string)
implement
counting_sort$key<record><intknd> entry =
entry.0
implement
main0 () =
let
val data =
$list{record}
('(8, "eight001"),
'(6, "six00001"),
'(6, "six00002"),
'(8, "eight002"),
'(1, "one00001"),
'(4, "four0001"),
'(2, "two00001"),
'(8, "eight003"))
var arr : @[record][8]
val () = array_initize_list<record> (arr, 8, data)
val () = counting_sort<record> (arr, i2sz 8, 1, 9)
var i : [i : nat | i <= 8] int i
in
for (i := 0; i <> 8; i := succ i)
println! (arr[i].0, " -> ", arr[i].1)
end</syntaxhighlight>
{{out}}
<pre>$ patscc -DATS_MEMALLOC_GCBDW -O3 counting_sort_task.dats -lgc && ./a.out
1 -> one00001
2 -> two00001
4 -> four0001
6 -> six00001
6 -> six00002
8 -> eight001
8 -> eight002
8 -> eight003</pre>
=={{header|AutoHotkey}}==
contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276465.html#276465 forum]
<
CountingSort(ints,min,max) {
Line 778 ⟶ 1,013:
}
Return SubStr(t,2)
}</
=={{header|BASIC256}}==
<syntaxhighlight lang="basic256">
# counting sort
Line 819 ⟶ 1,054:
next i
print
</syntaxhighlight>
=={{header|BBC BASIC}}==
<
test%() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
PROCcountingsort(test%(), -31, 782)
Line 844 ⟶ 1,079:
ENDWHILE
NEXT
ENDPROC</
'''Output:'''
<pre>
Line 851 ⟶ 1,086:
=={{header|C}}==
<
#include <stdlib.h>
Line 885 ⟶ 1,120:
}
}
}</
Testing (we suppose the oldest human being is less than 140 years old).
<
#define MAX_AGE 140
int main()
Line 899 ⟶ 1,134:
for(i=0; i < N; i++) printf("%d\n", ages[i]);
return EXIT_SUCCESS;
}</
=={{header|C sharp|C#}}==
<
using System.Linq;
Line 937 ⟶ 1,172:
}
}
}</
=={{header|C++}}==
<
#include <iostream>
#include <time.h>
Line 1,005 ⟶ 1,240:
}
//------------------------------------------------------------------------------
</
{{out}}
<pre>
Line 1,018 ⟶ 1,253:
Uses C++11. Compile with
g++ -std=c++11 counting.cpp
<
#include <iterator>
#include <iostream>
Line 1,047 ⟶ 1,282:
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}</
Output:
<pre>
Line 1,056 ⟶ 1,291:
Straightforward implementation of counting sort. By using <code>[http://www.lispworks.com/documentation/HyperSpec/Body/f_map.htm map]</code> and <code>[http://www.lispworks.com/documentation/HyperSpec/Body/f_map_in.htm map-into]</code>, counting sort can work efficiently on both lists and vectors. The closure given as the second argument to <code>map-into</code> returns the sorted elements of sequence. Because <code>map-into</code> will only call the function as many times as necessary to re-populate sequence, there is no need for bounds checking. <code>counts</code> is declared to have dynamic-extent and so a compiler might stack allocate it.
<
(max (reduce #'max sequence)))
(let ((i 0)
Line 1,067 ⟶ 1,302:
(incf i))
(decf (aref counts i))
(+ i min)))))</
=={{header|D}}==
<
void countingSort(int[] array, in size_t min, in size_t max)
Line 1,096 ⟶ 1,331:
countingSort(data, dataMin, dataMax);
assert(isSorted(data));
}</
=={{header|Delphi}}==
Line 1,103 ⟶ 1,338:
Straightforward implementation, no particularly interesting characteristics.
<
def counts := ([0] * (max - min + 1)).diverge()
for elem in array {
Line 1,115 ⟶ 1,350:
}
}
}</
<pre style="height:15ex;overflow:scroll">? def arr := [34,6,8,7,4,3,56,7,8,4,3,5,7,8,6,4,4,67,9,0,0,76,467,453,34,435,37,4,34,234,435,3,2,7,4,634,534,735,5,4,6,78,4].diverge()
Line 1,123 ⟶ 1,358:
? arr
# value: [0, 0, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 34, 34, 34, 37, 56, 67, 76, 78, 234, 435, 435, 453, 467, 534, 634, 735].diverge()</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
proc countsort min max . d[] .
len count[] max - min + 1
for n in d[]
count[n - min + 1] += 1
.
z = 1
for i = min to max
while count[i - min + 1] > 0
d[z] = i
z += 1
count[i - min + 1] -= 1
.
.
.
for i = 1 to 100
d[] &= randint 1000
.
countsort 1 1000 d[]
print d[]
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
Line 1,197 ⟶ 1,455:
end
</syntaxhighlight>
TEST:
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,240 ⟶ 1,498:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,250 ⟶ 1,508:
=={{header|Elena}}==
ELENA
<
import system'routines;
Line 1,264 ⟶ 1,522:
int z := 0;
count.populate::(int i => 0);
for(int i := 0
for(int i := min
{
while (count[i - min] > 0)
Line 1,283 ⟶ 1,541:
public program()
{
var list := new Range(0, 10).selectBy::(i => randomGenerator.
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.countingSort().asEnumerable())
}</
{{out}}
<pre>
Line 1,296 ⟶ 1,554:
=={{header|Elixir}}==
{{works with|Elixir|1.1}}
<
def counting_sort([]), do: []
def counting_sort(list) do
Line 1,309 ⟶ 1,567:
end
IO.inspect Sort.counting_sort([1,-2,-3,2,1,-5,5,5,4,5,9])</
{{out}}
Line 1,319 ⟶ 1,577:
{{works with|Fortran|95 and later}}
<
implicit none
Line 1,361 ⟶ 1,619:
end subroutine counting_sort_mm
end module CountingSort</
Testing:
<
use CountingSort
implicit none
Line 1,381 ⟶ 1,639:
write(*,'(I4)') ages
end program test</
=={{header|FreeBASIC}}==
<
Function findMax(array() As Integer) As Integer
Line 1,442 ⟶ 1,700:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,452 ⟶ 1,710:
=={{header|Go}}==
This version follows the task pseudocode above, with one more optimization.
<
import (
Line 1,496 ⟶ 1,754:
}
}
}</
This version follows the WP pseudocode. It can be adapted to sort items other than integers.
<
import (
Line 1,547 ⟶ 1,805:
}
copy(a, output)
}</
=={{header|Groovy}}==
Solution:
<
def max = array.max()
def min = array.min()
Line 1,558 ⟶ 1,816:
array.each { count[it] ++ }
(min..max).findAll{ count[it] }.collect{ [it]*count[it] }.flatten()
}</
Test:
<
println countingSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1])
Line 1,567 ⟶ 1,825:
println countingSort([34,6,8,7,4,3,56,7,8,4,3,5,7,8,6,4,4,67,9,0,0,76,467,453,34,435,37,4,34,234,435,3,2,7,4,634,534,-735,5,4,6,78,4])
// slo-o-o-o-ow due to unnecessarily large counting array
println countingSort([10000033,10000006,10000008,10000009,10000013,10000031,10000013,10000032,10000023,10000023,10000011,10000012,10000021])</
Output:
Line 1,579 ⟶ 1,837:
We use lists for input and output rather than arrays, since lists are used more often in Haskell.
<
countingSort :: (Ix n) => [n] -> n -> n -> [n]
countingSort l lo hi = concatMap (uncurry $ flip replicate) count
where count = assocs . accumArray (+) 0 (lo, hi) . map (\i -> (i, 1)) $ l</
=={{header|Haxe}}==
{{trans|C}}
<
public static function sort(arr:Array<Int>) {
var min = arr[0], max = arr[0];
Line 1,619 ⟶ 1,877:
Sys.println('Sorted Integers: ' + integerArray);
}
}</
{{out}}
Line 1,630 ⟶ 1,888:
The following example is hopefully in the spirit of a counting sort using a hash table as a substituted for a sparse array. Simply translating the pseudo-code would be very un-Iconish (as opposed to Uniconish).
<
write("Sorting Demo using ",image(countingsort))
writes(" on list : ")
Line 1,652 ⟶ 1,910:
every put(X := [],( 1 to T[i := lower to upper], i) ) # reconstitute with correct order and count
return X
end</
Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'display sort', and 'writex' from Bubble Sort]].
Line 1,662 ⟶ 1,920:
=={{header|Io}}==
{{trans|Java}}
<
countingSort := method(min, max,
count := list() setSize(max - min + 1) mapInPlace(0)
Line 1,685 ⟶ 1,943:
l := list(2, 3, -4, 5, 1)
l countingSortInPlace println # ==> list(-4, 1, 2, 3, 5)</
A more functional-like version:
<
fill := method(x, size,
/* Resizes list to a given size and fills it with a given value. */
Line 1,710 ⟶ 1,968:
l := list(2, 3, -4, 5, 1)
l countingSortInPlace println # ==> list(-4, 1, 2, 3, 5)</
=={{header|IS-BASIC}}==
<syntaxhighlight lang="is-basic">
100 PROGRAM "CountSrt.bas"
110 RANDOMIZE
Line 1,760 ⟶ 2,018:
540 LOOP
550 NEXT
560 END DEF</
=={{header|J}}==
{{eff note|J|/:~}}
<
min =. <./y
cnt =. 0 $~ 1+(>./y)-min
Line 1,771 ⟶ 2,029:
end.
cnt # min+i.#cnt
)</
Alternative implementation:
<
'''Example:'''
<
_2 _2 6 _1 1 6 _1 4 4 1 4 4 5 _3 5 3 0 _1 3 4
csort a
_3 _2 _2 _1 _1 _1 0 1 1 3 3 4 4 4 4 4 5 5 6 6</
And note that this can be further simplified if the range is known in advance (which could easily be the case -- this sorting mechanism is practical when we have a small fixed range of values that we are sorting). Here, we do not need to inspect the data to find min and max values, since they are already known:
<
(m+i.n-m) (+/@(=/)~ # [) ]
)</
or
<
(+/@(=/) # ])&(m+i.n-m)
)</
Example:
<
_3 _2 _2 _1 _1 _1 0 1 1 3 3 4 4 4 4 4 5 5 6 6</
=={{header|Java}}==
{{works with|Java|1.5+}}
<
int[] count= new int[max - min + 1];
for(int number : array){
Line 1,817 ⟶ 2,075:
}
}
}</
=={{header|JavaScript}}==
<
var i, z = 0, count = [];
Line 1,838 ⟶ 2,096:
}
}</
Testing:
<
var i, ages = [];
Line 1,854 ⟶ 2,112:
for (i = 0; i < 100; i++) {
document.write(ages[i] + "<br />");
}</
=={{header|jq}}==
Line 1,863 ⟶ 2,121:
object is used instead. This ensures the space requirement is just O(length). In jq, this approach is both time and space
efficient, except for the small cost of converting integers to strings, which is necessary because JSON keys must be strings.
<
. as $in
| reduce range(0;length) as $i
Line 1,877 ⟶ 2,135:
else reduce range(0; $hash[$s]) as $j (.; . + [$i])
end
);</
'''Example''':
<
{{out}}
<syntaxhighlight lang="sh">
$ jq -M -c -n -f counting_sort.jq
[0,1,1,2,4,10]</
=={{header|Julia}}==
Line 1,889 ⟶ 2,147:
This is a translation of the pseudocode presented in the task description, accounting for the fact that Julia arrays start indexing at 1 rather than zero and taking care to return a result of the same type as the input. Note that <code>cnt</code> has the machine's standard integer type (typically <code>Int64</code>), which need not match that of the input.
<
lo, hi = extrema(a)
b = zeros(a)
Line 1,908 ⟶ 2,166:
println("# unsorted bytes: $v\n -> sorted bytes: $(countsort(v))")
v = rand(1:2 ^ 10, 20)
println("# unsorted integers: $v\n -> sorted integers: $(countsort(v))")</
{{out}}
Line 1,917 ⟶ 2,175:
=={{header|Kotlin}}==
<
fun countingSort(array: IntArray) {
Line 1,938 ⟶ 2,196:
countingSort(array)
println("Sorted : ${array.asList()}")
}</
{{out}}
Line 1,947 ⟶ 2,205:
=={{header|langur}}==
<syntaxhighlight lang="langur">
val countingSort = fn(zlist) {
val mi, ma = minmax(zlist)
var cnt = [0] * (ma-mi+1)
for i in zlist { cnt[i-mi+1] += 1 }
}
val
writeln "Original: ",
writeln "Sorted : ",
</syntaxhighlight>
{{out}}
Line 1,967 ⟶ 2,224:
=={{header|Lua}}==
<
local min, max = math.min( unpack(f) ), math.max( unpack(f) )
local count = {}
Line 1,996 ⟶ 2,253:
for i in next, f do
print( f[i] )
end</
=={{header|M4}}==
<
define(`randSeed',141592653)
Line 2,034 ⟶ 2,291:
show(`a')
countingsort(`a',0,99)
show(`a')</
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
minElem = Min[list]; maxElem = Max[list];
count = ConstantArray[0, (maxElem - minElem + 1)];
Line 2,048 ⟶ 2,305:
count[[i - minElem + 1]] = count[[i - minElem + 1]] - 1;]
];
]</
<pre>countingSort@{2, 3, 1, 5, 7, 6}
->{1, 2, 3, 5, 6, 7}</pre>
Line 2,055 ⟶ 2,312:
This is a direct translation of the pseudo-code, except to compensate for MATLAB using 1 based arrays.
<
minElem = min(list);
Line 2,076 ⟶ 2,333:
end
end %countingSort</
Sample Usage:
<
ans =
1 2 3 4 5 6</
=={{header|MAXScript}}==
<syntaxhighlight lang="maxscript">
fn countingSort arr =
(
Line 2,109 ⟶ 2,366:
)
return arr
)</
{{out}}
<syntaxhighlight lang="maxscript">
a = for i in 1 to 15 collect random 1 30
#(7, 1, 6, 16, 27, 11, 24, 16, 25, 11, 22, 7, 28, 15, 17)
countingSort a
#(1, 6, 7, 7, 11, 11, 15, 16, 16, 17, 22, 24, 25, 27, 28)
</syntaxhighlight>
=={{header|Modula-3}}==
<
IMPORT IO, Fmt;
Line 2,159 ⟶ 2,416:
END;
IO.Put("\n");
END Counting.</
Output:
<pre>
Line 2,168 ⟶ 2,425:
=={{header|Nanoquery}}==
{{trans|Java}}
<
count = {0} * (max - min + 1)
Line 2,183 ⟶ 2,440:
end
end
end</
=={{header|NetRexx}}==
===Version 1===
An almost direct implementation of the pseudocode.
<
options replace format comments java crossref savelog symbols binary
Line 2,257 ⟶ 2,514:
return array
</syntaxhighlight>
{{out}}
<pre style="overflow: scroll;">
Line 2,266 ⟶ 2,523:
===Version 2===
A more Rexx-like (and shorter) version. Due to NetRexx's built in indexed string capability, negative values are also easily supported.
<
options replace format comments java crossref symbols nobinary
Line 2,316 ⟶ 2,573:
return
</syntaxhighlight>
{{out}}
<pre>
Line 2,324 ⟶ 2,581:
=={{header|Nim}}==
<
let range = max - min + 1
var count = newSeq[T](range)
Line 2,338 ⟶ 2,595:
var a = @[5, 3, 1, 7, 4, 1, 1, 20]
countingSort(a, 1, 20)
echo a</
Output:
<pre>@[1, 1, 1, 3, 4, 5, 7, 20]</pre>
=={{header|Oberon-2}}==
{{trans|Modula-3}}
<syntaxhighlight lang="oberon2">MODULE CS;
IMPORT Out;
VAR
A:ARRAY 8 OF INTEGER;
I:LONGINT;
PROCEDURE Init(VAR A:ARRAY OF INTEGER);
BEGIN
A[0] := 80; A[1] := 10; A[2] := 40; A[3] := 60;
A[4] := 50; A[5] := 30; A[6] := 20; A[7] := 70;
END Init;
PROCEDURE CountingSort(VAR A:ARRAY OF INTEGER; Min,Max:INTEGER);
VAR
I,Z,Range:LONGINT;
Count:POINTER TO ARRAY OF INTEGER;
BEGIN
Range := Max - Min + 1;
NEW(Count, Range);
Z := 0;
FOR I := 0 TO LEN(A)-1 DO
INC(Count[A[I] - Min]);
END;
FOR I := Min TO Max DO
WHILE(Count[I - Min] > 0) DO
A[Z] := SHORT(I);
INC(Z);
DEC(Count[I - Min]);
END;
END;
END CountingSort;
BEGIN
Init(A);
CountingSort(A, 10, 80);
FOR I := 0 TO LEN(A)-1 DO
Out.Int(A[I],0); Out.String(" ");
END;
Out.Ln;
END CS.
</syntaxhighlight>
=={{header|Objeck}}==
<
bundle Default {
class Cocktail {
Line 2,374 ⟶ 2,677:
}
}
</syntaxhighlight>
=={{header|OCaml}}==
For arrays:
<
let count = Array.make (hi-lo+1) 0 in
Array.iter (fun i -> count.(i-lo) <- count.(i-lo) + 1) arr;
Array.concat (Array.to_list (Array.mapi (fun i x -> Array.make x (lo+i)) count))</
=={{header|Octave}}==
This implements the same algorithm but in a more compact way (using the same loop to count and to ''update'' the sorted vector). This implementation is ''elegant'' (and possible since the sort is not done "in place"), but not so efficient on machines that can't parallelize some operations (the vector <tt>arr</tt> is scanned for every value between <tt>minval</tt> and <tt>maxval</tt>)
<
r = arr;
z = 1;
Line 2,394 ⟶ 2,697:
endwhile
endfor
endfunction</
Testing:
<
sorted = counting_sort(ages, 0, 140);
disp(sorted);</
=={{header|Oz}}==
Using arrays as in the original algorithm. The implementation is slightly simpler because arrays can start with an arbitrary index in Oz.
<
proc {CountingSort Arr Min Max}
Count = {Array.new Min Max 0}
Line 2,427 ⟶ 2,730:
in
{CountingSort A 1 9}
{Show {Array.toRecord unit A}}</
Using lists for input and output and a dictionary as a sparse array:
<
fun {CountingSort Xs}
Count = {Dictionary.new}
Line 2,450 ⟶ 2,753:
end
in
{Show {CountingSort [3 1 4 1 5 9 2 6 5]}}</
=={{header|PARI/GP}}==
<
my(u=vector(#v),i=0);
for(n=mn,mx,
Line 2,459 ⟶ 2,762:
);
u
};</
=={{header|Pascal}}==
<
procedure counting_sort(var arr : Array of Integer; n, min, max : Integer);
Line 2,493 ⟶ 2,796:
for i := 0 to 99 do
writeln(ages[i]);
end.</
=={{header|Perl}}==
<
use strict;
Line 2,509 ⟶ 2,812:
my $i = $min;
@$a = map {($i++) x $_} @cnt;
}</
Testing:
<
counting_sort(\@ages, 0, 140);
print join("\n", @ages), "\n";</
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 2,540 ⟶ 2,843:
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">20</span><span style="color: #0000FF;">}</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">countingSort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">))</span>
<!--</
{{out}}
<pre>
Line 2,548 ⟶ 2,851:
=={{header|PHP}}==
<
function counting_sort(&$arr, $min, $max)
Line 2,568 ⟶ 2,871:
}
}
}</
Testing:
<
for($i=0; $i < 100; $i++) {
array_push($ages, rand(0, 140));
Line 2,581 ⟶ 2,884:
echo $ages[$i] . "\n";
}
?></
=={{header|PicoLisp}}==
<
(let Count (need (- Max Min -1) 0)
(for N Lst
Line 2,593 ⟶ 2,896:
(do (car C) (link (car I))) )
Count
(range Min Max) ) ) ) )</
Output:
Line 2,600 ⟶ 2,903:
=={{header|PL/I}}==
<
declare A(*) fixed;
declare (min, max) fixed;
Line 2,628 ⟶ 2,931:
end;
end;
end count_sort;</
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function countingSort($array) {
$minmax = $array | Measure-Object -Minimum -Maximum
Line 2,653 ⟶ 2,956:
"$array"
"$(countingSort $array)"
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 2,661 ⟶ 2,964:
=={{header|PureBasic}}==
<
Define i, j
Dim c(max - min)
Line 2,676 ⟶ 2,979:
Wend
Next
EndProcedure</
=={{header|Python}}==
Follows the spirit of the counting sort but uses Pythons defaultdict(int) to initialize array accesses to zero, and list concatenation:
<
>>> def countingSort(array, mn, mx):
count = defaultdict(int)
Line 2,693 ⟶ 2,996:
>>> mini,maxi = 1,10
>>> countingSort(data, mini, maxi) == sorted(data)
True</
Using a list:
{{works with|Python|2.6}}
<
cnt = [0] * (max - min + 1)
for x in a:
Line 2,703 ⟶ 3,006:
return [x for x, n in enumerate(cnt, start=min)
for i in xrange(n)]</
=={{header|Quackery}}==
<
unrot poke ] is [1+] ( [ n --> [ )
Line 2,727 ⟶ 3,030:
dup say "Before: " echo cr
10 19 csort
say "After: " echo</
{{out}}
Line 2,736 ⟶ 3,039:
=={{header|R}}==
{{trans|Octave}}
<
r <- arr
z <- 1
Line 2,755 ⟶ 3,058:
ages <- floor(runif(100, 0, 140+1))
sorted <- counting_sort(ages, 0, 140)
print(sorted)</
=={{header|Racket}}==
<
#lang racket
Line 2,771 ⟶ 3,074:
(counting-sort (vector 0 9 3 8 1 -1 1 2 3 7 4) -1 10)
</syntaxhighlight>
Output:
<
'#(-1 0 1 1 2 3 3 4 7 8 9)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|rakudo|2018.03}}
<syntaxhighlight lang="raku"
my $off = @ints.min;
(my @counts)[$_ - $off]++ for @ints;
Line 2,792 ⟶ 3,095:
say @ages.sort;
say @ages.&counting-sort.join eq @ages.sort.join ?? 'ok' !! 'not ok';</
{{out}}
<pre>(5 5 5 7 9 17 19 19 20 21 25 27 28 30 32 34 38 40 41 45 48 49 50 51 53 54 55 56 59 62 65 66 67 69 70 73 74 81 83 85 87 91 91 93 94 96 99 99 100 101)
Line 2,804 ⟶ 3,107:
Negative, zero, and positive integers are supported.
===version 1===
<
$= '1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 8 25 43 62 42 63 41 18 42 17 43 16 44 15 45 14 46 79 113 78 114 77 39 78 38'
#= words($); w= length(#); !.= 0 /* [↑] a list of some Recaman numbers.*/
Line 2,821 ⟶ 3,124:
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do s=1 for #; say right("element",20) right(s,w) arg(1) right(@.s,m); end; return</
{{out|output|text= when using the default input:}}
Line 2,912 ⟶ 3,215:
===version 2===
{{trans|PL/I}}
<
* 13.07.2014 Walter Pachl translated from PL/I
* 27.05.2023 Walter Pachl take care of bad lists
*--------------------------------------------------------------------*/
Parse Arg alist
If alist='*' Then
alist='999 888 777 1 5 13 15 17 19 21 5'
Select
When alist='' Then Call exit 'List is empty'
When words(alist)=1 Then Call exit 'List has only one element:' alist
Otherwise Nop
End
Parse Var alist lo hi .
Do i=1 By 1 While alist<>''
Line 2,962 ⟶ 3,267:
End
Say ol
Return
exit:
Say arg(1)
</syntaxhighlight>
'''Output:'''
<pre>before count_sort
Line 2,970 ⟶ 3,279:
=={{header|Ring}}==
<
aList = [4, 65, 2, 99, 83, 782, 1]
see countingSort(aList, 1, 782)
Line 2,993 ⟶ 3,302:
next
return f
</syntaxhighlight>
=={{header|RPL}}==
{{works with|RPL|HP-49C}}
« { } → in bins
« in « MIN » STREAM DUP
in « MAX » STREAM
'''FOR''' j
'bins'
'''IF''' in j POS
'''THEN''' 0 in + « j == + » STREAM
'''ELSE''' 0 '''END'''
STO+
'''NEXT'''
{ }
1 bins SIZE '''FOR''' j
OVER j + 1 - 'bins' j GET NDUPN →LIST +
'''NEXT''' NIP
» '<span style="color:blue">CSORT</span>' STO
{ -5 1 0 5 7 5 1 2 -3 1 } <span style="color:blue">CSORT</span>
{{out}}
<pre>
1: { -5 -3 0 1 1 1 2 5 5 7 }
</pre>
Counting sort is 17 times slower than the <code>SORT</code> built-in function on an HP-50g.
=={{header|Ruby}}==
<
def counting_sort!
replace counting_sort
Line 3,016 ⟶ 3,350:
# => [-3, -1, 9, -6, -8, -3, 5, -7, 4, 0, 5, 0, 2, -2, -6, 10, -10, -7, 5, -7]
p ary.counting_sort
# => [-10, -8, -7, -7, -7, -6, -6, -3, -3, -2, -1, 0, 0, 2, 4, 5, 5, 5, 9, 10]</
=={{header|Rust}}==
<
mut data: Vec<usize>,
min: usize,
Line 3,053 ⟶ 3,387:
let arr3 = vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
println!("{:?}", counting_sort(arr3, 0, 10));
}</
{{out}}
<pre>
Line 3,062 ⟶ 3,396:
=={{header|Scala}}==
<
input.foldLeft(Array.fill(max - min + 1)(0)) { (arr, n) =>
arr(n - min) += 1
Line 3,068 ⟶ 3,402:
}.zipWithIndex.foldLeft(List[Int]()) {
case (lst, (cnt, ndx)) => List.fill(cnt)(ndx + min) ::: lst
}.reverse</
It's better (i.e. slightly faster) to reverse the frequencies list before processing it, instead of the whole result
<
input.foldLeft(Array.fill(max - min + 1)(0)) { (arr, n) =>
arr(n - min) += 1
Line 3,077 ⟶ 3,411:
}.zipWithIndex.reverse.foldLeft(List[Int]()) {
case (lst, (cnt, ndx)) => List.fill(cnt)(ndx + min) ::: lst
}</
=={{header|Sidef}}==
<
var cnt = ([0] * (max - min + 1))
a.each {|i| cnt[i-min]++ }
Line 3,087 ⟶ 3,421:
var a = 100.of { 100.irand }
say counting_sort(a, 0, 100)</
=={{header|Slate}}==
<
[| counts index |
min `defaultsTo: (s reduce: #min: `er).
Line 3,106 ⟶ 3,440:
].
s
].</
=={{header|Smalltalk}}==
{{works with|GNU Smalltalk}}
<
countingSortWithMin: min andMax: max [
|oc z|
Line 3,127 ⟶ 3,461:
]
]
].</
Testing:
<
ages := OrderedCollection new.
Line 3,140 ⟶ 3,474:
ages countingSortWithMin: 0 andMax: 140.
ages printNl.</
=={{header|Tcl}}==
{{works with|Tcl|8.5}}
<
# If either of min or max weren't given, compute them now
if {$min eq ""} {
Line 3,184 ⟶ 3,518:
for {set i 0} {$i < 50} {incr i} {lappend a [expr {1+ int(rand()*10)}]}
puts $a
puts [countingsort $a]</
<pre>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
1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 5 5 5 5 5 5 6 6 6 6 7 7 7 7 7 7 8 8 8 8 9 9 9 9 9 9 10 10 10 10
Line 3,190 ⟶ 3,524:
=={{header|VBA}}==
{{trans|Phix}}<
Private Function countingSort(array_ As Variant, mina As Long, maxa As Long) As Variant
Dim count() As Integer
Line 3,210 ⟶ 3,544:
s = [{5, 3, 1, 7, 4, 1, 1, 20}]
Debug.Print Join(countingSort(s, WorksheetFunction.Min(s), WorksheetFunction.Max(s)), ", ")
End Sub</
<pre>1, 1, 1, 3, 4, 5, 7, 20</pre>
Line 3,217 ⟶ 3,551:
=====Implementation=====
<
dim num
dim max
Line 3,258 ⟶ 3,592:
next
countingSort = a
end function</
=====Invocation=====
<
a = array(300, 1, -2, 3, -4, 5, -6, 7, -8, 100, 11 )
wscript.echo join( a, ", " )
countingSort a
wscript.echo join( a, ", " )</
=====Output=====
Line 3,273 ⟶ 3,607:
</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">fn counting_sort(mut arr []int, min int, max int) {
println('Input: ' + arr.str())
mut count := [0].repeat(max - min + 1)
Line 3,297 ⟶ 3,631:
mut arr := [6, 2, 1, 7, 6, 8]
counting_sort(mut arr, 1, 8)
}</
{{out}}
<pre>Input: [6, 2, 1, 7, 6, 8]
Line 3,303 ⟶ 3,637:
=={{header|Wren}}==
<
var count = List.filled(max - min + 1, 0)
for (n in a) count[n - min] = count[n - min] + 1
Line 3,321 ⟶ 3,655:
var max = a.reduce { |max, i| (i > max) ? i : max }
countingSort.call(a, min, max)
System.print("Sorted : %(a)")</
{{out}}
Line 3,330 ⟶ 3,664:
=={{header|XPL0}}==
<
proc CountingSort(Array, Min, Max, Size); \Sort Array
Line 3,352 ⟶ 3,686:
CountingSort(A, -5, 9, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]</
{{out}}
Line 3,358 ⟶ 3,692:
-5 1 1 2 3 4 4 5 6 9
</pre>
=={{header|Yabasic}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">dim array(15)
a = 0
b = arraysize(array(),1)
for i = a to b
array(i) = ran(1000)
next i
print "unsort ";
printArray(array())
mx = findMax(array())
mn = findMin(array())
countingSort(array(), mn, mx) // ordenar el array
print " sort ";
printArray(array())
end
sub findMax(array())
local length, i
length = arraysize(array(),1) - 1
if length = 0 return 0
if length = 1 return array(0)
mx = 0
for i = 1 to arraysize(array(),1)
if array(i) > mx mx = array(i)
next i
return mx
end sub
sub findMin(array())
local length, i
length = arraysize(array(),1) - 1
if length = 0 return 0
if length = 1 return array(0)
mn = 0
for i = 1 to arraysize(array(),1)
if array(i) < mn mn = array(i)
next i
return mn
end sub
sub countingSort(array(), mn, mx)
local number, z, i, ub
dim count(mx - mn)
ub = arraysize(array(),1)
for i = 0 to ub
number = array(i)
count(number - mn) = count(number - mn) + 1
next
z = 0
for i = mn to mx
while count(i - mn) > 0
array(z) = i
z = z + 1
count(i - mn) = count(i - mn) - 1
wend
next i
end sub
sub printArray(array())
for i = 0 to arraysize(array(),1)
print array(i) using("####");
if i = b then print ""; else print ", "; : fi
next i
print
end sub</syntaxhighlight>
=={{header|zkl}}==
<
count:=(max - min + 1).pump(List().write,0); // array of (max - min + 1) zeros
foreach number in (array){
Line 3,370 ⟶ 3,779:
}
array
}</
<
countingSort(array,(0).min(array), (0).max(array)).println();</
{{out}}
<pre>L(-31,0,1,2,2,4,65,83,99,182)</pre>
|