Sorting algorithms/Counting sort: Difference between revisions
→{{header|langur}}
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Langurmonkey (talk | contribs) |
||
(16 intermediate revisions by 11 users not shown) | |||
Line 452:
=={{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 1,325 ⟶ 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}}==
Line 1,452 ⟶ 1,508:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 1,466 ⟶ 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,485 ⟶ 1,541:
public program()
{
var list := new Range(0, 10).selectBy::(i => randomGenerator.
console.printLine("before:", list.asEnumerable());
Line 2,149 ⟶ 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 2,543 ⟶ 2,598:
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}}==
Line 3,114 ⟶ 3,215:
===version 2===
{{trans|PL/I}}
<syntaxhighlight lang="rexx">/* REXX ---------------------------------------------------------------
* 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 3,164 ⟶ 3,267:
End
Say ol
Return
exit:
Say arg(1)
</syntaxhighlight>
'''Output:'''
<pre>before count_sort
Line 3,196 ⟶ 3,303:
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}}==
Line 3,475 ⟶ 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,505 ⟶ 3,637:
=={{header|Wren}}==
<syntaxhighlight lang="
var count = List.filled(max - min + 1, 0)
for (n in a) count[n - min] = count[n - min] + 1
Line 3,560 ⟶ 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}}==
|