Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
Line 876: | Line 876: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=={{header|Eiffel}}== |
|||
<lang Eiffel> |
|||
class |
|||
HEAPSORT |
|||
feature |
|||
sort_array (ar: ARRAY [INTEGER]) |
|||
-- Sorts array 'ar' in ascending order. |
|||
local |
|||
i, j, r, l, m, n: INTEGER |
|||
sorted: BOOLEAN |
|||
do |
|||
n := ar.count |
|||
j := 0 |
|||
i := 0 |
|||
m := 0 |
|||
r := n |
|||
l := (n // 2)+1 |
|||
from |
|||
until |
|||
sorted |
|||
loop |
|||
if l > 1 then |
|||
l := l - 1 |
|||
m := ar.item (l) |
|||
else |
|||
m := ar.item (r) |
|||
ar.put (ar.item (1), r) |
|||
r := r - 1 |
|||
if r = 1 then |
|||
ar.put (m, 1) |
|||
sorted := True |
|||
end |
|||
end |
|||
if not sorted then |
|||
i := l |
|||
j := l * 2 |
|||
from |
|||
until |
|||
j > r |
|||
loop |
|||
if (j < r) and (ar.item (j) < ar.item (j + 1)) then |
|||
j := j + 1 |
|||
end |
|||
if m < ar.item (j) then |
|||
ar.put (ar.item (j), i) |
|||
i := j |
|||
j := j + i |
|||
else |
|||
j := r + 1 |
|||
end |
|||
end |
|||
ar.put (m, i) |
|||
end |
|||
end |
|||
end |
|||
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] > ar [i + 1] then |
|||
Result := False |
|||
end |
|||
i := i + 1 |
|||
end |
|||
end |
|||
end |
|||
</lang> |
|||
Test: |
|||
<lang Eiffel> |
|||
class |
|||
APPLICATION |
|||
create |
|||
make |
|||
feature |
|||
make |
|||
local |
|||
test: ARRAY [INTEGER] |
|||
do |
|||
create test.make_empty |
|||
test := <<5, 91, 13, 99,7, 35>> |
|||
io.put_string ("Unsorted: ") |
|||
across |
|||
test as t |
|||
loop |
|||
io.put_string (t.item.out + " ") |
|||
end |
|||
io.new_line |
|||
create heap_sort |
|||
heap_sort.sort_array (test) |
|||
io.put_string ("Sorted: ") |
|||
across |
|||
test as t |
|||
loop |
|||
io.put_string (t.item.out + " ") |
|||
end |
|||
end |
|||
heap_sort: HEAPSORT |
|||
end |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Unsorted: 5 91 13 99 7 35 |
|||
Sorted: 5 7 13 35 91 99 |
|||
</pre> |
|||
=={{header|F Sharp|F#}}== |
=={{header|F Sharp|F#}}== |