Sorting algorithms/Counting sort: Difference between revisions
Content added Content deleted
(→{{header|Ada}}: Marked as incorrect because this is not the counting sort algorithm; seems like the requirements were misunderstood) |
(→{{header|Ada}}: Changed to meet the task requirements) |
||
Line 452: | Line 452: | ||
=={{header|Ada}}== |
=={{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. |
|||
with Ada.Numerics; use Ada.Numerics; |
|||
with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; |
|||
procedure Counting_Sort is |
procedure Counting_Sort is |
||
type Data is array (Integer range <>) of Natural; |
type Data is array (Integer range <>) of Natural; |
||
procedure Sort(Item : out Data) is |
procedure Sort(Item : in out Data) is |
||
minValue, maxValue: Natural; |
|||
begin |
begin |
||
minValue := Item(Item'First); maxValue := Item(Item'First); |
|||
Item |
for I in Item'Range loop |
||
if Item(I) < minValue then minValue := Item(I); end if; |
|||
if Item(I) > maxValue then maxValue := Item(I); end if; |
|||
end loop; |
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; |
end Sort; |
||
Stuff : Data(1.. |
Stuff : Data(1..30); |
||
Seed : Generator; |
|||
begin |
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); |
Sort(Stuff); |
||
Put("After : "); |
|||
for I in Stuff'range loop |
for I in Stuff'range loop |
||
Put(Natural'Image(Stuff(I))); |
Put(Natural'Image(Stuff(I))); |
||
end loop; |
end loop; |
||
New_Line; |
New_Line; |
||
end Counting_Sort; |
end Counting_Sort; |
||
</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}}== |
=={{header|ALGOL 68}}== |