Rosetta Code

Sorting algorithms/Counting sort: Difference between revisions

Page Discussion

Sorting algorithms/Counting sort (view source)

Revision as of 21:17, 14 June 2024

3,067 bytes added ,  12 days ago
→‎{{header|langur}}
(→‎{{header|Ada}}: Marked as incorrect because this is not the counting sort algorithm; seems like the requirements were misunderstood)
 
(11 intermediate revisions by 7 users not shown)
Line 452:
 
=={{header|Ada}}==
<syntaxhighlight lang="ada">
{{incorrect|Ada}}
with Ada.Text_Io; use Ada.Text_Io;
Given that we know the range of data, the problem really reduces to initializing the array to the ordered range of values. The input order is irrelevant.
<syntaxhighlight lang="ada">with Ada.Text_IoNumerics; use Ada.Text_IoNumerics;
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
forminValue I in:= Item(Item'rangeFirst); loopmaxValue := Item(Item'First);
for I in Item(I)'Range := I;loop
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..14030);
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>
</syntaxhighlight>
===Output===
 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
{{out}}
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
<pre>
98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
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
133 134 135 136 137 138 139 140
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,326 ⟶ 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,453 ⟶ 1,508:
 
=={{header|Elena}}==
ELENA 46.x :
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 1,467 ⟶ 1,522:
int z := 0;
count.populate::(int i => 0);
for(int i := 0,; i < self.Length,; i += 1) { count[self[i] - min] := count[self[i] - min] + 1 };
for(int i := min,; i <= max,; i += 1)
{
while (count[i - min] > 0)
Line 1,486 ⟶ 1,541:
public program()
{
var list := new Range(0, 10).selectBy::(i => randomGenerator.evalnextInt(10)).toArray();
console.printLine("before:", list.asEnumerable());
Line 2,150 ⟶ 2,205:
 
=={{header|langur}}==
<syntaxhighlight lang="langur">
{{works with|langur|0.10}}
val countingSort = fn(zlist) {
Prior to 0.10, multi-variable declaration/assignment would use parentheses around variable names and values.
val mi, ma = minmax(zlist)
 
var cnt = [0] * (ma-mi+1)
<syntaxhighlight lang="langur">val .countingSort = f(.array) {
for i in zlist { cnt[i-mi+1] += 1 }
val .min, .max = minmax(.array)
varfor .counti of cnt { _for ~= arrcnt[i] .max-.min* [i+mi-1,] 0}
for .i in .array { .count[.i-.min+1] += 1 }
for .i of .count { _for ~= arr .count[.i], .i+.min-1 }
}
 
val .data = [7, 234, -234, 9, 43, 123, 14]
 
writeln "Original: ", .data
writeln "Sorted : ", .countingSort(.data)</syntaxhighlight>
</syntaxhighlight>
 
{{out}}
Line 3,249 ⟶ 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,558 ⟶ 3,637:
 
=={{header|Wren}}==
<syntaxhighlight lang="ecmascriptwren">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
Line 3,613 ⟶ 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}}==
Langurmonkey
1,006

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/349588...365375"