Sorting algorithms/Counting sort: Difference between revisions

Content added Content deleted
(→‎{{header|jq}}: space requirement is O(length))
Line 441:
 
<lang Eiffel>
 
class
COUNTING_SORT
 
feature
 
sort(ar: ARRAY[INTEGER]; min, max: INTEGER): ARRAY[INTEGER]
sort (ar: ARRAY [INTEGER]; min, max: INTEGER): ARRAY [INTEGER]
local
-- Sorted Array in ascending order.
count: ARRAY[INTEGER]
require
i, j, z: INTEGER
ar_not_void: ar /= Void
do
lowest_index_zero: ar.lower = 0
create count.make_filled (0, 0, max-min)
fromlocal
count: ARRAY [INTEGER]
i:= 0
i, j, z: INTEGER
until
do
i= ar.count
create Result.make_empty
loop
Result.deep_copy (ar)
count[ar[i]-min]:= count[ar[i]-min]+1
create count.make_filled (0, 0, max - min)
i:= i+1
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
 
across count as c loop io.put_string (c.item.out + "%T") end
feature {NONE}
z:= 0
 
from i:= min
is_sorted (ar: ARRAY [INTEGER]): BOOLEAN
until i>max
--- Is 'ar' sorted in ascending order?
loop
require
from j:= 0
ar_not_empty: ar.is_empty = FALSE
until j= count[i-min]
local
i: INTEGER
do
Result := TRUE
from
i := ar.lower
until
i = ar.upper
loop
if ar [zi]:= > ar [i + 1] then
z RESULT := z+1FALSE
j:= j+1end
i := i + 1
end
i:= i+1
end
 
Result:= ar
end
end
 
</lang>
TEST:
Line 480 ⟶ 517:
class
APPLICATION
 
inherit
ARGUMENTS
create
make
 
feature
 
make
do
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 as t loop io.put_string (t.item.out + "unsorted:%TN") end
across
create count
test:=count.sort (test, -7,as 6)t
loop
across test as ar loop io.put_string (ar.item.out+"%T") end
io.put_string (t.item.out + "%T")
end
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]
test: ARRAY [INTEGER]
 
end
 
</lang>
{{out}}
Line 508 ⟶ 561:
-7 1 2 3 4 6
</pre>
 
=={{header|Fortran}}==
{{works with|Fortran|95 and later}}
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort"