Sorting algorithms/Counting sort: Difference between revisions

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

local

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)

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

if ar [i] > ar [i + 1] then

RESULT := FALSE

end

i := i + 1

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

io.put_string ("unsorted:%N")

across

test as t

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

test: ARRAY [INTEGER]