Sorting algorithms/Heapsort: Difference between revisions
Add CLU
Not a robot (talk | contribs) (Add Draco) |
Not a robot (talk | contribs) (Add CLU) |
||
Line 1,501:
user> (heapsort (list 1 2 4 6 2 3 6))
[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}}==
| |||