Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
Not a robot (talk | contribs) (Add Draco) |
Not a robot (talk | contribs) (Add CLU) |
||
Line 1,501: | Line 1,501: | ||
user> (heapsort (list 1 2 4 6 2 3 6)) |
user> (heapsort (list 1 2 4 6 2 3 6)) |
||
[1 2 2 3 4 6 6]</lang> |
[1 2 2 3 4 6 6]</lang> |
||
=={{header|CLU}}== |
|||
<lang clu>% Sort an array in place using heap-sort. The contained type |
|||
% may be any type that can be compared. |
|||
heapsort = cluster [T: type] is sort |
|||
where T has lt: proctype (T,T) returns (bool) |
|||
rep = null |
|||
aT = array[T] |
|||
sort = proc (a: aT) |
|||
% CLU arrays may start at any index. |
|||
% For simplicity, we will store the old index, |
|||
% reindex the array at zero, do the heap-sort, |
|||
% then undo the reindexing. |
|||
% This should be a constant-time operation. |
|||
old_low: int := aT$low(a) |
|||
aT$set_low(a, 0) |
|||
heapsort_(a) |
|||
aT$set_low(a, old_low) |
|||
end sort |
|||
% Heap-sort a zero-indexed array |
|||
heapsort_ = proc (a: aT) |
|||
heapify(a) |
|||
end_: int := aT$high(a) |
|||
while end_ > 0 do |
|||
swap(a, end_, 0) |
|||
end_ := end_ - 1 |
|||
siftDown(a, 0, end_) |
|||
end |
|||
end heapsort_ |
|||
heapify = proc (a: aT) |
|||
start: int := (aT$high(a) - 1) / 2 |
|||
while start >= 0 do |
|||
siftDown(a, start, aT$high(a)) |
|||
start := start - 1 |
|||
end |
|||
end heapify |
|||
siftDown = proc (a: aT, start, end_: int) |
|||
root: int := start |
|||
while root*2 + 1 <= end_ do |
|||
child: int := root * 2 + 1 |
|||
if child + 1 <= end_ cand a[child] < a[child + 1] then |
|||
child := child + 1 |
|||
end |
|||
if a[root] < a[child] then |
|||
swap(a, root, child) |
|||
root := child |
|||
else |
|||
break |
|||
end |
|||
end |
|||
end siftDown |
|||
swap = proc (a: aT, i, j: int) |
|||
temp: T := a[i] |
|||
a[i] := a[j] |
|||
a[j] := temp |
|||
end swap |
|||
end heapsort |
|||
% Print an array |
|||
print_arr = proc [T: type] (s: stream, a: array[T], w: int) |
|||
where T has unparse: proctype (T) returns (string) |
|||
for e: T in array[T]$elements(a) do |
|||
stream$putright(s, T$unparse(e), w) |
|||
end |
|||
stream$putl(s, "") |
|||
end print_arr |
|||
% Test the heapsort |
|||
start_up = proc () |
|||
po: stream := stream$primary_output() |
|||
arr: array[int] := array[int]$[9, -5, 3, 3, 24, -16, 3, -120, 250, 17] |
|||
stream$puts(po, "Before sorting: ") |
|||
print_arr[int](po,arr,5) |
|||
heapsort[int]$sort(arr) |
|||
stream$puts(po, "After sorting: ") |
|||
print_arr[int](po,arr,5) |
|||
end start_up</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|COBOL}}== |
=={{header|COBOL}}== |