Anonymous user
Sorting algorithms/Counting sort: Difference between revisions
→{{header|Eiffel}}
(→{{header|jq}}: space requirement is O(length)) |
|||
Line 441:
<lang Eiffel>
class
COUNTING_SORT
feature
sort (ar: ARRAY [INTEGER]; min, max: INTEGER): ARRAY [INTEGER]
-- Sorted Array in ascending order.
require
ar_not_void: ar /= Void
lowest_index_zero: ar.lower = 0
count: ARRAY [INTEGER]
i, j, z: INTEGER
do
create Result.make_empty
Result.deep_copy (ar)
create count.make_filled (0, 0, max - min)
from
i := 0
until
i = Result.count
loop
count [Result [i] - min] := count [Result [i] - min] + 1
i := i + 1
end
z := 0
from
i := min
until
i > max
loop
from
j := 0
until
j = count [i - min]
loop
Result [z] := i
z := z + 1
j := j + 1
end
i := i + 1
end
ensure
Result_is_sorted: is_sorted (Result)
end
feature {NONE}
is_sorted (ar: ARRAY [INTEGER]): BOOLEAN
--- Is 'ar' sorted in ascending order?
require
ar_not_empty: ar.is_empty = FALSE
local
i: INTEGER
do
Result := TRUE
from
i := ar.lower
until
i = ar.upper
loop
if ar [
i := i + 1
end
end
end
</lang>
TEST:
Line 480 ⟶ 517:
class
APPLICATION
create
feature
make
create test.make_filled (0, 0, 5)
test [0] := -7
test [1] := 4
test [2] := 2
test [3] := 6
test [4] := 1
test [5] := 3
across
test
loop
io.put_string (t.item.out + "%T")
end
io.new_line
io.put_string ("sorted:%N")
create count
test := count.sort (test, -7, 6)
across
test as ar
loop
io.put_string (ar.item.out + "%T")
end
end
count: COUNTING_SORT
test: ARRAY [INTEGER]
end
</lang>
{{out}}
Line 508 ⟶ 561:
-7 1 2 3 4 6
</pre>
=={{header|Fortran}}==
{{works with|Fortran|95 and later}}
|