Sorting algorithms/Heapsort: Difference between revisions

== Icon and Unicon ==

==={{header|Icon}}===

<lang Icon>

procedure main() #: demonstrate various ways to sort a list and string

demosort(heapsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

end

procedure heapsort(X,op) #: return sorted list ascending(or descending)

local head,tail

op := sortop(op,X) # select how and what we sort

every head := (tail := *X) / 2 to 1 by -1 do # work back from from last parent node

X := siftdown(X,op,head,tail) # sift down from head to make the heap

every tail := *X to 2 by -1 do { # work between the beginning and the tail to final positions

X[1] :=: X[tail]

X := siftdown(X,op,1,tail-1) # re-sift next (previous) branch after shortening the heap

}

return X

end

procedure siftdown(X,op,root,tail) #: the value @root is moved "down" the path of max(min) value to its level

local child

while (child := root * 2) <= tail do { # move down the branch from root to tail

if op(X[child],X[tail >= child + 1]) then # choose the larger(smaller)

child +:= 1 # ... child

if op(X[root],X[child]) then { # root out of order?

X[child] :=: X[root]

root := child # follow max(min) branch

}

else

return X

}

return X

end</lang>

Algorithm notes:

* This is a fairly straight forward implementation of the pseudo-code with 'heapify' coded in-line.

Implementation notes:

* Since this transparently sorts both string and list arguments the result must 'return' to bypass call by value (strings)

* Beware missing trailing 'returns' when translating pseudo-code. For amusement try comment out the return at the end of 'shiftdown'

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'sortop', and 'demosort' in Bubble Sort]].

Sample Output:<pre>Sorting Demo using procedure heapsort

on list : [ 3 14 1 5 9 2 6 3 ]

with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms)

with op = "numeric": [ 1 2 3 3 5 6 9 14 ] (0 ms)

with op = "string": [ 1 14 2 3 3 5 6 9 ] (0 ms)

with op = ">>": [ 9 6 5 3 3 2 14 1 ] (0 ms)

with op = ">": [ 14 9 6 5 3 3 2 1 ] (0 ms)

with op = procedure cmp: [ 1 2 3 3 5 6 9 14 ] (0 ms)

with op = "cmp": [ 1 2 3 3 5 6 9 14 ] (0 ms)

on string : "qwerty"

with op = &null: "eqrtwy" (0 ms)</pre>

==={{header|Unicon}}===

The Icon solution works in Unicon.