Sorting algorithms/Counting sort: Difference between revisions
→{{header|langur}}
Langurmonkey (talk | contribs) |
Langurmonkey (talk | contribs) |
||
| (36 intermediate revisions by 23 users not shown) | |||
Line 1:
{{task|Sorting Algorithms}}
[[Category:Sorting]]
{{Sorting Algorithm}}
{{Wikipedia|Counting sort}}
Line 5 ⟶ 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 27 ⟶ 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>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight 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))</syntaxhighlight>
{{out}}
<pre>
1B
</pre>
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* Counting sort - 18/04/2020
COUNTS CSECT
USING COUNTS,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R6,A i=1
DO WHILE=(C,R6,LE,=A(N)) do i=1 to hbound(a)
L R8,0(R6) a(i)
S R8,MIN k=a(i)-min
LR R1,R8 k
SLA R1,2 ~
L R3,COUNT(R1) count(k+1)
LA R3,1(R3) +1
ST R3,COUNT(R1) count(k+1)+=1
LA R6,4(R6) i++
ENDDO , enddo i
LA R7,A j=1
L R6,MIN i=min
DO WHILE=(C,R6,LE,MAX) do i=min to max
LR R8,R6 i
S R8,MIN k=i-min
WHILEC LR R1,R8 while k
SLA R1,2 ..... ~
L R2,COUNT(R1) ..... count(k+1)
LTR R2,R2 ..... test
BNP WHENDC ..... count(k+1)>0
ST R6,0(R7) a(j)=i
LA R7,4(R7) j++
LR R1,R8 k
SLA R1,2 ~
L R3,COUNT(R1) count(k+1)
BCTR R3,0 -1
ST R3,COUNT(R1) count(k+1)-=1
B WHILEC end while
WHENDC AH R6,=H'1' i++
ENDDO , enddo i
LA R9,PG @buffer
LA R6,A i=1
DO WHILE=(C,R6,LE,=A(N)) do i=1 to hbound(a)
L R2,0(R6) a(i)
XDECO R2,XDEC edit a(i)
MVC 0(3,R9),XDEC+9 output a(i)
LA R9,3(R9) @buffer++
LA R6,4(R6) i++
ENDDO , enddo i
XPRNT PG,L'PG print buffer
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
MIN DC F'-9' min
MAX DC F'99' max
A DC F'98',F'35',F'15',F'46',F'6',F'64',F'92',F'44'
DC F'53',F'21',F'56',F'74',F'13',F'11',F'92',F'70'
DC F'43',F'2',F'-7',F'89',F'22',F'82',F'41',F'91'
DC F'28',F'51',F'0',F'39',F'29',F'34',F'15',F'26'
N DC A((N-A)/L'A) hbound(a)
PG DC CL96' ' buffer
XDEC DS CL12 temp fo xdeco
COUNT DC 200F'0' count
REGEQU
END COUNTS </syntaxhighlight>
{{out}}
<pre>
-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}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program countSort64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
#Caution : number strictly positive and not too big
TableNumber: .quad 1,3,6,2,5,9,10,8,4,5
//TableNumber: .quad 10,9,8,7,6,5,4,3,2,1
.equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrTableNumber // address number table
mov x1,NBELEMENTS // number of élements
bl searchMinMax
mov x3,NBELEMENTS
bl countSort
ldr x0,qAdrTableNumber // address number table
bl displayTable
ldr x0,qAdrTableNumber // address number table
mov x1,NBELEMENTS // number of élements
bl isSorted // control sort
cmp x0,1 // sorted ?
beq 1f
ldr x0,qAdrszMessSortNok // no !! error sort
bl affichageMess
b 100f
1: // yes
ldr x0,qAdrszMessSortOk
bl affichageMess
100: // standard end of the program
mov x0,0 // return code
mov x8,EXIT // request to exit program
svc 0 // perform the system call
qAdrsZoneConv: .quad sZoneConv
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrTableNumber: .quad TableNumber
qAdrszMessSortOk: .quad szMessSortOk
qAdrszMessSortNok: .quad szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements > 0 */
/* x0 return table address r1 return min r2 return max */
searchMinMax:
stp x3,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
mov x3,x1 // save size
mov x1,1<<62 // min
mov x2,0 // max
mov x4,0 // index
1:
ldr x5,[x0,x4,lsl 3]
cmp x5,x1
csel x1,x5,x1,lt
cmp x5,x2
csel x2,x5,x2,gt
add x4,x4,1
cmp x4,x3
blt 1b
100:
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x3,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements > 0 */
/* x0 return 0 if not sorted 1 if sorted */
isSorted:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
mov x2,0
ldr x4,[x0,x2,lsl 3]
1:
add x2,x2,1
cmp x2,x1
bge 99f
ldr x3,[x0,x2, lsl 3]
cmp x3,x4
blt 98f
mov x4,x3
b 1b
98:
mov x0,0 // not sorted
b 100f
99:
mov x0,1 // sorted
100:
ldp x3,x4,[sp],16 // restaur 2 registers
ldp x2,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* count sort */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the minimum */
/* x2 contains the maximum */
/* x3 contains area size */
/* caution : the count area is in the stack. if max is very large, risk of error */
countSort:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
stp x8,x9,[sp,-16]! // save registers
sub x3,x3,1 // compute endidx = n - 1
sub x5,x2,x1 // compute max - min
add x5,x5,1 // + 1
lsl x9,x5,3 // 8 bytes by number
sub sp,sp,x9 // reserve count area in stack
mov fp,sp // frame pointer = stack
mov x6,0
mov x4,0
1: // loop init stack area
str x6,[fp,x4, lsl 3]
add x4,x4,#1
cmp x4,x5
blt 1b
mov x4,#0 // indice
2: // start loop 2
ldr x5,[x0,x4,lsl 3] // load value A[j]
sub x5,x5,x1 // - min
ldr x6,[fp,x5,lsl 3] // load count of value
add x6,x6,1 // increment counter
str x6,[fp,x5,lsl 3] // and store
add x4,x4,1 // increment indice
cmp x4,x3 // end ?
ble 2b // no -> loop 2
mov x7,0 // z
mov x4,x1 // index = min
3: // start loop 3
sub x6,x4,x1 // compute index - min
ldr x5,[fp,x6,lsl 3] // load count
4: // start loop 4
cmp x5,0 // count <> zéro
beq 5f
str x4,[x0,x7,lsl 3] // store value A[j]
add x7,x7,1 // increment z
sub x5,x5,1 // decrement count
b 4b
5:
add x4,x4,1 // increment index
cmp x4,x2 // max ?
ble 3b // no -> loop 3
add sp,sp,x9 // stack alignement
100:
ldp x8,x9,[sp],16 // restaur 2 registers
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* x0 contains the address of table */
displayTable:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x2,x0 // table address
mov x3,0
1: // loop display table
ldr x0,[x2,x3,lsl 3]
ldr x1,qAdrsZoneConv
bl conversion10S // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
add x3,x3,1
cmp x3,NBELEMENTS - 1
ble 1b
ldr x0,qAdrszCarriageReturn
bl affichageMess
mov x0,x2 // table address
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|Action!}}==
<syntaxhighlight lang="action!">DEFINE MAXSIZE="100"
PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC CountingSort(INT ARRAY a INT size,min,max)
INT ARRAY count(MAXSIZE)
INT n,i,num,z
n=max-min+1
FOR i=0 TO n-1
DO count(i)=0 OD
FOR i=0 TO size-1
DO
num=a(i)
count(num-min)==+1
OD
z=0
FOR i=min TO max
DO
WHILE count(i-min)>0
DO
a(z)=i
z==+1
count(i-min)==-1
OD
OD
RETURN
PROC Test(INT ARRAY a INT size,min,max)
PrintE("Array before sort:")
PrintArray(a,size)
CountingSort(a,size,min,max)
PrintE("Array after sort:")
PrintArray(a,size)
PutE()
RETURN
PROC Main()
INT ARRAY
a(10)=[1 4 65535 0 3 7 4 8 20 65530],
b(21)=[10 9 8 7 6 5 4 3 2 1 0
65535 65534 65533 65532 65531
65530 65529 65528 65527 65526],
c(8)=[101 102 103 104 105 106 107 108],
d(12)=[1 65535 1 65535 1 65535 1
65535 1 65535 1 65535]
Test(a,10,-6,20)
Test(b,21,-10,10)
Test(c,8,101,108)
Test(d,12,-1,1)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Counting_sort.png Screenshot from Atari 8-bit computer]
<pre>
Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]
Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]
Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]
Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
</pre>
=={{header|ActionScript}}==
<
{
var count:Array = new Array(array.length);
Line 46 ⟶ 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 82 ⟶ 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 121 ⟶ 557:
FOR i TO UPB ages DO print((" ", whole(ages[i],0))) OD;
print(new line)
)</
Sample output:
0 1 2 3 3 4 4 5 6 7 8 9 9 10 11 12 15 18 18 19 21 21 22 27 33 35 36 38 38 38 38 39 40 40 41 43 44 53 54 55 57 57 58 59 59 60 60 60 60 61 62 64 65 66 67 68 70 71 78 79 82 83 84 84 87 87 88 88 88 89 89 92 93 93 97 98 99 99 100 107 109 114 115 115 118 122 126 127 127 129 129 130 131 133 134 136 136 137 139 139
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program countSort.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
.include "../../ficmacros.s"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
#Caution : number stritcly positive and not too big
#TableNumber: .int 1,3,6,2,5,9,10,8,5,7 @ for test 2 sames values
TableNumber: .int 10,9,8,7,6,5,4,3,2,1
.equ NBELEMENTS, (. - TableNumber) / 4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
bl searchMinMax @ r1=min r2=max
mov r3,#NBELEMENTS @ number of élements
bl countSort
ldr r0,iAdrTableNumber @ address number table
bl displayTable
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
bl isSorted @ control sort
cmp r0,#1 @ sorted ?
beq 2f
ldr r0,iAdrszMessSortNok @ no !! error sort
bl affichageMess
b 100f
2: @ yes
ldr r0,iAdrszMessSortOk
bl affichageMess
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessResult: .int sMessResult
iAdrTableNumber: .int TableNumber
iAdrszMessSortOk: .int szMessSortOk
iAdrszMessSortNok: .int szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the éléments number */
/* r0 return address r1 return min r2 return max */
searchMinMax:
push {r3-r5,lr} @ save registers
mov r3,r1 @ save size
mov r1,#1<<30 @ min
mov r2,#0 @ max
mov r4,#0 @ index
1:
ldr r5,[r0,r4, lsl #2] @ load value
cmp r5,r1 @ if < min
movlt r1,r5
cmp r5,r2 @ if > max
movgt r2,r5
add r4,r4,#1 @ increment index
cmp r4,r3 @ end ?
blt 1b @ no -> loop
100:
pop {r3-r5,lr}
bx lr @ return
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements > 0 */
/* r0 return 0 if not sorted 1 if sorted */
isSorted:
push {r2-r4,lr} @ save registers
mov r2,#0
ldr r4,[r0,r2,lsl #2]
1:
add r2,#1
cmp r2,r1
movge r0,#1
bge 100f
ldr r3,[r0,r2, lsl #2]
cmp r3,r4
movlt r0,#0
blt 100f
mov r4,r3
b 1b
100:
pop {r2-r4,lr}
bx lr @ return
/******************************************************************/
/* count Sort */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the minimum */
/* r2 contains the maximun */
/* r3 contains elements number */
/* caution : the count area is in the stack. if max is very large, risk of error */
countSort:
push {r1-r9,lr} @ save registers
sub r3,r3,#1 @ compute end index
sub r5,r2,r1 @ compute max - min
add r5,r5,#1 @ + 1
lsl r9,r5,#2 @ 4 bytes by number
sub sp,sp,r9 @ reserve area on stack
mov fp,sp @ frame pointer = stack address
mov r6,#0
mov r4,#0
1: @ loop init stack area
str r6,[fp,r4, lsl #2]
add r4,r4,#1
cmp r4,r5
blt 1b
mov r4,#0 @ indice
2: @ start loop 2
ldr r5,[r0,r4,lsl #2] @ load value A[j]
sub r5,r5,r1 @ - min
ldr r6,[fp,r5,lsl #2] @ load count of value
add r6,r6,#1 @ increment counter
str r6,[fp,r5,lsl #2] @ and store
add r4,#1 @ increment indice
cmp r4,r3 @ end ?
ble 2b @ no -> loop 2
mov r7,#0 @ z
mov r4,r1 @ indice = min
//bl displayTable
3: @ loop 3
sub r6,r4,r1 @ compute index - min
ldr r5,[fp,r6,lsl #2] @ load count
4: @ loop 4
cmp r5,#0 @ cont <> zero
beq 5f
str r4,[r0,r7,lsl #2] @ store value
add r7,r7,#1 @ increment z
sub r5,r5,#1 @ decrement count
b 4b
5:
add r4,r4,#1 @ decrement indice
cmp r4,r2 @ max ?
ble 3b @ no -> loop 3
add sp,sp,r9 @ stack alignement
100:
pop {r1-r9,lr}
bx lr @ return
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* r0 contains the address of table */
displayTable:
push {r0-r3,lr} @ save registers
mov r2,r0 @ table address
mov r3,#0
1: @ loop display table
ldr r0,[r2,r3,lsl #2]
ldr r1,iAdrsZoneConv @
bl conversion10S @ décimal conversion
ldr r0,iAdrsMessResult
ldr r1,iAdrsZoneConv @ insert conversion
bl strInsertAtCharInc
bl affichageMess @ display message
add r3,#1
cmp r3,#NBELEMENTS - 1
ble 1b
ldr r0,iAdrszCarriageReturn
bl affichageMess
mov r0,r2
100:
pop {r0-r3,lr}
bx lr
iAdrsZoneConv: .int sZoneConv
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">countingSort: function [items, minimum, maximum][
a: new items
rng: inc maximum - minimum
cnt: array.of: rng 0
z: 0
loop 0..dec size a 'i [
mm: a\[i]-minimum
cnt\[mm]: cnt\[mm] + 1
]
loop minimum..maximum 'i [
loop 0..dec cnt\[i-minimum] 'j [
a\[z]: i
z: z + 1
]
]
return a
]
print countingSort [3 1 2 8 5 7 9 4 6] 1 9</syntaxhighlight>
{{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 141 ⟶ 1,013:
}
Return SubStr(t,2)
}</
=={{header|BASIC256}}==
<syntaxhighlight lang="basic256">
# counting sort
Line 182 ⟶ 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 207 ⟶ 1,079:
ENDWHILE
NEXT
ENDPROC</
'''Output:'''
<pre>
Line 214 ⟶ 1,086:
=={{header|C}}==
<
#include <stdlib.h>
Line 248 ⟶ 1,120:
}
}
}</
Testing (we suppose the oldest human being is less than 140 years old).
<
#define MAX_AGE 140
int main()
Line 262 ⟶ 1,134:
for(i=0; i < N; i++) printf("%d\n", ages[i]);
return EXIT_SUCCESS;
}</
=={{header|C sharp|C#}}==
<
using System.Linq;
Line 300 ⟶ 1,172:
}
}
}</
=={{header|C++}}==
<
#include <iostream>
#include <time.h>
Line 368 ⟶ 1,240:
}
//------------------------------------------------------------------------------
</
{{out}}
<pre>
Line 381 ⟶ 1,253:
Uses C++11. Compile with
g++ -std=c++11 counting.cpp
<
#include <iterator>
#include <iostream>
Line 410 ⟶ 1,282:
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}</
Output:
<pre>
Line 419 ⟶ 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 430 ⟶ 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 459 ⟶ 1,331:
countingSort(data, dataMin, dataMax);
assert(isSorted(data));
}</
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort#Pascal Pascal].
=={{header|E}}==
Straightforward implementation, no particularly interesting characteristics.
<
def counts := ([0] * (max - min + 1)).diverge()
for elem in array {
Line 476 ⟶ 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 484 ⟶ 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 558 ⟶ 1,455:
end
</syntaxhighlight>
TEST:
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 601 ⟶ 1,498:
end
</syntaxhighlight>
{{out}}
<pre>
Line 611 ⟶ 1,508:
=={{header|Elena}}==
ELENA
<
import system'routines;
Line 625 ⟶ 1,522:
int z := 0;
count.populate::(int i => 0);
for(int i := 0
for(int i := min
{
while (count[i - min] > 0)
Line 644 ⟶ 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 657 ⟶ 1,554:
=={{header|Elixir}}==
{{works with|Elixir|1.1}}
<
def counting_sort([]), do: []
def counting_sort(list) do
Line 670 ⟶ 1,567:
end
IO.inspect Sort.counting_sort([1,-2,-3,2,1,-5,5,5,4,5,9])</
{{out}}
Line 680 ⟶ 1,577:
{{works with|Fortran|95 and later}}
<
implicit none
Line 722 ⟶ 1,619:
end subroutine counting_sort_mm
end module CountingSort</
Testing:
<
use CountingSort
implicit none
Line 742 ⟶ 1,639:
write(*,'(I4)') ages
end program test</
=={{header|FreeBASIC}}==
<
Function findMax(array() As Integer) As Integer
Line 803 ⟶ 1,700:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 813 ⟶ 1,710:
=={{header|Go}}==
This version follows the task pseudocode above, with one more optimization.
<
import (
Line 857 ⟶ 1,754:
}
}
}</
This version follows the WP pseudocode. It can be adapted to sort items other than integers.
<
import (
Line 908 ⟶ 1,805:
}
copy(a, output)
}</
=={{header|Groovy}}==
Solution:
<
def max = array.max()
def min = array.min()
Line 919 ⟶ 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 928 ⟶ 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 940 ⟶ 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 980 ⟶ 1,877:
Sys.println('Sorted Integers: ' + integerArray);
}
}</
{{out}}
Line 991 ⟶ 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,013 ⟶ 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,023 ⟶ 1,920:
=={{header|Io}}==
{{trans|Java}}
<
countingSort := method(min, max,
count := list() setSize(max - min + 1) mapInPlace(0)
Line 1,046 ⟶ 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,071 ⟶ 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,121 ⟶ 2,018:
540 LOOP
550 NEXT
560 END DEF</
=={{header|J}}==
{{eff note|J|/:~}}
<
min =. <./y
cnt =. 0 $~ 1+(>./y)-min
Line 1,132 ⟶ 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,178 ⟶ 2,075:
}
}
}</
=={{header|JavaScript}}==
<
var i, z = 0, count = [];
Line 1,199 ⟶ 2,096:
}
}</
Testing:
<
var i, ages = [];
Line 1,215 ⟶ 2,112:
for (i = 0; i < 100; i++) {
document.write(ages[i] + "<br />");
}</
=={{header|jq}}==
Line 1,224 ⟶ 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,238 ⟶ 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,250 ⟶ 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,269 ⟶ 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,278 ⟶ 2,175:
=={{header|Kotlin}}==
<
fun countingSort(array: IntArray) {
Line 1,299 ⟶ 2,196:
countingSort(array)
println("Sorted : ${array.asList()}")
}</
{{out}}
Line 1,308 ⟶ 2,205:
=={{header|langur}}==
<syntaxhighlight lang="langur">val .countingSort = fn(.list) {
val .min, .max = minmax(.list)
var .count = [0] * (.max-.min+1)
for .i in .list { .count[.i-.min+1] += 1 }
for .i of .count { _for ~= .count[.i] * [.i+.min-1] }
}
Line 1,321 ⟶ 2,215:
writeln "Original: ", .data
writeln "Sorted : ", .countingSort(.data)
</syntaxhighlight>
{{out}}
Line 1,328 ⟶ 2,223:
=={{header|Lua}}==
<
local min, max = math.min( unpack(f) ), math.max( unpack(f) )
local count = {}
Line 1,357 ⟶ 2,252:
for i in next, f do
print( f[i] )
end</
=={{header|M4}}==
<
define(`randSeed',141592653)
Line 1,395 ⟶ 2,290:
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 1,409 ⟶ 2,304:
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 1,417 ⟶ 2,311:
This is a direct translation of the pseudo-code, except to compensate for MATLAB using 1 based arrays.
<
minElem = min(list);
Line 1,438 ⟶ 2,332:
end
end %countingSort</
Sample Usage:
<
ans =
1 2 3 4 5 6</
=={{header|MAXScript}}==
<syntaxhighlight lang="maxscript">
fn countingSort arr =
(
Line 1,471 ⟶ 2,365:
)
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 1,521 ⟶ 2,415:
END;
IO.Put("\n");
END Counting.</
Output:
<pre>
Line 1,530 ⟶ 2,424:
=={{header|Nanoquery}}==
{{trans|Java}}
<
count = {0} * (max - min + 1)
Line 1,545 ⟶ 2,439:
end
end
end</
=={{header|NetRexx}}==
===Version 1===
An almost direct implementation of the pseudocode.
<
options replace format comments java crossref savelog symbols binary
Line 1,619 ⟶ 2,513:
return array
</syntaxhighlight>
{{out}}
<pre style="overflow: scroll;">
Line 1,628 ⟶ 2,522:
===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 1,678 ⟶ 2,572:
return
</syntaxhighlight>
{{out}}
<pre>
Line 1,686 ⟶ 2,580:
=={{header|Nim}}==
<
let range = max - min + 1
var count = newSeq[T](range)
var z = 0
for i in 0 ..
for i in min .. max:
for j in 0 ..<
a[z] = i
inc z
Line 1,700 ⟶ 2,594:
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 1,736 ⟶ 2,676:
}
}
</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 1,756 ⟶ 2,696:
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 1,789 ⟶ 2,729:
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 1,812 ⟶ 2,752:
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 1,821 ⟶ 2,761:
);
u
};</
=={{header|Pascal}}==
<
procedure counting_sort(var arr : Array of Integer; n, min, max : Integer);
Line 1,855 ⟶ 2,795:
for i := 0 to 99 do
writeln(ages[i]);
end.</
=={{header|Perl}}==
<
use strict;
Line 1,871 ⟶ 2,811:
my $i = $min;
@$a = map {($i++) x $_} @cnt;
}</
Testing:
<
counting_sort(\@ages, 0, 140);
print join("\n", @ages), "\n";</
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">countingSort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">array</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">mina</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxa</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxa</span><span style="color: #0000FF;">-</span><span style="color: #000000;">mina</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">array</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">array</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">array</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">count</span><span style="color: #0000FF;">[</span><span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">mina</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">mina</span> <span style="color: #008080;">to</span> <span style="color: #000000;">maxa</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">mina</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">z</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">i</span>
<span style="color: #000000;">z</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">array</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,905 ⟶ 2,850:
=={{header|PHP}}==
<
function counting_sort(&$arr, $min, $max)
Line 1,925 ⟶ 2,870:
}
}
}</
Testing:
<
for($i=0; $i < 100; $i++) {
array_push($ages, rand(0, 140));
Line 1,938 ⟶ 2,883:
echo $ages[$i] . "\n";
}
?></
=={{header|PicoLisp}}==
<
(let Count (need (- Max Min -1) 0)
(for N Lst
Line 1,950 ⟶ 2,895:
(do (car C) (link (car I))) )
Count
(range Min Max) ) ) ) )</
Output:
Line 1,957 ⟶ 2,902:
=={{header|PL/I}}==
<
declare A(*) fixed;
declare (min, max) fixed;
Line 1,985 ⟶ 2,930:
end;
end;
end count_sort;</
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function countingSort($array) {
$minmax = $array | Measure-Object -Minimum -Maximum
Line 2,010 ⟶ 2,955:
"$array"
"$(countingSort $array)"
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 2,018 ⟶ 2,963:
=={{header|PureBasic}}==
<
Define i, j
Dim c(max - min)
Line 2,033 ⟶ 2,978:
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,050 ⟶ 2,995:
>>> 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,060 ⟶ 3,005:
return [x for x, n in enumerate(cnt, start=min)
for i in xrange(n)]</
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ 2dup peek 1+
unrot poke ] is [1+] ( [ n --> [ )
[ 1+ dip tuck -
rot 0 swap of
swap rot witheach
[ over +
rot swap [1+]
swap ]
negate swap
[] swap witheach
[ dip [ over i^ + ]
of join ]
nip ] is csort ( [ n n --> [ )
[] 15 times
[ 10 random 10 + join ]
dup say "Before: " echo cr
10 19 csort
say "After: " echo</syntaxhighlight>
{{out}}
<pre>Before: [ 16 14 15 10 19 18 12 16 12 14 10 13 12 15 18 ]
After: [ 10 10 12 12 12 13 14 14 15 15 16 16 18 18 19 ]</pre>
=={{header|R}}==
{{trans|Octave}}
<
r <- arr
z <- 1
Line 2,083 ⟶ 3,057:
ages <- floor(runif(100, 0, 140+1))
sorted <- counting_sort(ages, 0, 140)
print(sorted)</
=={{header|Racket}}==
<
#lang racket
Line 2,099 ⟶ 3,073:
(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,120 ⟶ 3,094:
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,132 ⟶ 3,106:
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(#);
m=
do
end /*
/*W: max index width for the
call show 'before sort: '; say copies('▓',
call countSort #
call show ' after sort: ' /*show the after array elements. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
countSort: parse arg N; x= 1; do k=LO to HI;
end /*k*/
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,196 ⟶ 3,169:
element 39 before sort: 78
element 40 before sort: 38
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
element 1 after sort: 1
element 2 after sort: 2
Line 2,240 ⟶ 3,213:
===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,283 ⟶ 3,266:
End
Say ol
Return
exit:
Say arg(1)
</syntaxhighlight>
'''Output:'''
<pre>before count_sort
Line 2,291 ⟶ 3,278:
=={{header|Ring}}==
<
aList = [4, 65, 2, 99, 83, 782, 1]
see countingSort(aList, 1, 782)
Line 2,314 ⟶ 3,301:
next
return f
</syntaxhighlight>
=={{header|Ruby}}==
<
def counting_sort!
replace counting_sort
Line 2,337 ⟶ 3,324:
# => [-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 2,374 ⟶ 3,361:
let arr3 = vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
println!("{:?}", counting_sort(arr3, 0, 10));
}</
{{out}}
<pre>
Line 2,383 ⟶ 3,370:
=={{header|Scala}}==
<
input.foldLeft(Array.fill(max - min + 1)(0)) { (arr, n) =>
arr(n - min) += 1
Line 2,389 ⟶ 3,376:
}.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 2,398 ⟶ 3,385:
}.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 2,408 ⟶ 3,395:
var a = 100.of { 100.irand }
say counting_sort(a, 0, 100)</
=={{header|Slate}}==
<
[| counts index |
min `defaultsTo: (s reduce: #min: `er).
Line 2,427 ⟶ 3,414:
].
s
].</
=={{header|Smalltalk}}==
{{works with|GNU Smalltalk}}
<
countingSortWithMin: min andMax: max [
|oc z|
Line 2,448 ⟶ 3,435:
]
]
].</
Testing:
<
ages := OrderedCollection new.
Line 2,461 ⟶ 3,448:
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 2,505 ⟶ 3,492:
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 2,511 ⟶ 3,498:
=={{header|VBA}}==
{{trans|Phix}}<
Private Function countingSort(array_ As Variant, mina As Long, maxa As Long) As Variant
Dim count() As Integer
Line 2,531 ⟶ 3,518:
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 2,538 ⟶ 3,525:
=====Implementation=====
<
dim num
dim max
Line 2,579 ⟶ 3,566:
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 2,594 ⟶ 3,581:
</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">fn counting_sort(
println('Input: ' + arr.str())
mut count := [0].repeat(max - min + 1)
Line 2,618 ⟶ 3,605:
mut arr := [6, 2, 1, 7, 6, 8]
counting_sort(mut arr, 1, 8)
}</
{{out}}
<pre>Input: [6, 2, 1, 7, 6, 8]
Output: [1, 2, 6, 6, 7, 8]</pre>
=={{header|Wren}}==
<syntaxhighlight lang="wren">var countingSort = Fn.new { |a, min, max|
var count = List.filled(max - min + 1, 0)
for (n in a) count[n - min] = count[n - min] + 1
var z = 0
for (i in min..max) {
while (count[i - min] > 0) {
a[z] = i
z = z + 1
count[i - min] = count[i - min] - 1
}
}
}
var a = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
System.print("Unsorted: %(a)")
var min = a.reduce { |min, i| (i < min) ? i : min }
var max = a.reduce { |max, i| (i > max) ? i : max }
countingSort.call(a, min, max)
System.print("Sorted : %(a)")</syntaxhighlight>
{{out}}
<pre>
Unsorted: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
Sorted : [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]
</pre>
=={{header|XPL0}}==
<
proc CountingSort(Array, Min, Max, Size); \Sort Array
Line 2,646 ⟶ 3,660:
CountingSort(A, -5, 9, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]</
{{out}}
Line 2,654 ⟶ 3,668:
=={{header|zkl}}==
<
count:=(max - min + 1).pump(List().write,0); // array of (max - min + 1) zeros
foreach number in (array){
Line 2,664 ⟶ 3,678:
}
array
}</
<
countingSort(array,(0).min(array), (0).max(array)).println();</
{{out}}
<pre>L(-31,0,1,2,2,4,65,83,99,182)</pre>
| |||