Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
Not a robot (talk | contribs) (Add Draco) |
|||
Line 1,831: | Line 1,831: | ||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
See [https://rosettacode.org/wiki/Sorting_algorithms/Heapsort#Pascal Pascal]. |
See [https://rosettacode.org/wiki/Sorting_algorithms/Heapsort#Pascal Pascal]. |
||
=={{header|Draco}}== |
|||
<lang draco>proc nonrec siftDown([*] int a; word start, end) void: |
|||
word root, child; |
|||
int temp; |
|||
bool stop; |
|||
root := start; |
|||
stop := false; |
|||
while not stop and root*2 + 1 <= end do |
|||
child := root*2 + 1; |
|||
if child+1 <= end and a[child] < a[child + 1] then |
|||
child := child + 1 |
|||
fi; |
|||
if a[root] < a[child] then |
|||
temp := a[root]; |
|||
a[root] := a[child]; |
|||
a[child] := temp; |
|||
root := child |
|||
else |
|||
stop := true |
|||
fi |
|||
od |
|||
corp |
|||
proc nonrec heapify([*] int a; word count) void: |
|||
word start; |
|||
bool stop; |
|||
start := (count - 2) / 2; |
|||
stop := false; |
|||
while not stop do |
|||
siftDown(a, start, count-1); |
|||
if start=0 |
|||
then stop := true /* avoid having to use a signed index */ |
|||
else start := start - 1 |
|||
fi |
|||
od |
|||
corp |
|||
proc nonrec heapsort([*] int a) void: |
|||
word end; |
|||
int temp; |
|||
heapify(a, dim(a,1)); |
|||
end := dim(a,1) - 1; |
|||
while end > 0 do |
|||
temp := a[0]; |
|||
a[0] := a[end]; |
|||
a[end] := temp; |
|||
end := end - 1; |
|||
siftDown(a, 0, end) |
|||
od |
|||
corp |
|||
/* Test */ |
|||
proc nonrec main() void: |
|||
int i; |
|||
[10] int a = (9, -5, 3, 3, 24, -16, 3, -120, 250, 17); |
|||
write("Before sorting: "); |
|||
for i from 0 upto 9 do write(a[i]:5) od; |
|||
writeln(); |
|||
heapsort(a); |
|||
write("After sorting: "); |
|||
for i from 0 upto 9 do write(a[i]:5) od |
|||
corp</lang> |
|||
{{out}} |
|||
<pre>Before sorting: 9 -5 3 3 24 -16 3 -120 250 17 |
|||
After sorting: -120 -16 -5 3 3 3 9 17 24 250</pre> |
|||
=={{header|E}}== |
=={{header|E}}== |