Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted
Line 885: Line 885:
sort_array (ar: ARRAY [INTEGER])
sort_array (ar: ARRAY [INTEGER])
-- Sorts array 'ar' in ascending order.
-- Sorts array 'ar' in ascending order.
require
not_empty: ar.count > 0
local
local
i, j, r, l, m, n: INTEGER
i, j, r, l, m, n: INTEGER
Line 901: Line 903:
if l > 1 then
if l > 1 then
l := l - 1
l := l - 1
m := ar.item (l)
m := ar[l]
else
else
m := ar.item (r)
m := ar[r]
ar.put (ar.item (1), r)
ar[r] := ar[1]
r := r - 1
r := r - 1
if r = 1 then
if r = 1 then
ar.put (m, 1)
ar[1]:=m
sorted := True
sorted := True
end
end
Line 918: Line 920:
j > r
j > r
loop
loop
if (j < r) and (ar.item (j) < ar.item (j + 1)) then
if (j < r) and (ar[j] < ar[j + 1]) then
j := j + 1
j := j + 1
end
end
if m < ar.item (j) then
if m < ar[j] then
ar.put (ar.item (j), i)
ar[i]:= ar[j]
i := j
i := j
j := j + i
j := j + i
Line 929: Line 931:
end
end
end
end
ar.put (m, i)
ar[i]:= m
end
end
end
end
ensure

sorted: is_sorted(ar)
end
end


Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Heapsort"