Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted
(Added XPL0 example.)
Line 2,220: Line 2,220:


<syntaxhighlight lang="text">
<syntaxhighlight lang="text">
func sort . d[] .
proc sort . d[] .
n = len d[]
n = len d[]
# make heap
# make heap
for i = 2 to n
for i = 2 to n
if d[i] > d[(i + 1) div 2]
if d[i] > d[(i + 1) div 2]
j = i
j = i
repeat
repeat
h = (j + 1) div 2
h = (j + 1) div 2
until d[j] <= d[h]
until d[j] <= d[h]
swap d[j] d[h]
swap d[j] d[h]
j = h
j = h
.
.
.
.
.
for i = n downto 2
.
for i = n downto 2
swap d[1] d[i]
swap d[1] d[i]
j = 1
j = 1
ind = 2
ind = 2
while ind < i
while ind < i
if ind + 1 < i and d[ind + 1] > d[ind]
if ind + 1 < i and d[ind + 1] > d[ind]
ind += 1
ind += 1
.
if d[j] < d[ind]
swap d[j] d[ind]
.
j = ind
ind = 2 * j
.
.
.
if d[j] < d[ind]
swap d[j] d[ind]
.
j = ind
ind = 2 * j
.
.
.
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]