Sorting algorithms/Heapsort: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
imported>SerErris |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (7 intermediate revisions by 5 users not shown) | |||
Line 2,251:
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
print data[]
</syntaxhighlight>
Line 2,919:
}</syntaxhighlight>
This is a better to read version. It includes comments and much better to understand and read function headers and loops.
It also has better readable variable names and can therefore be better used for study purposes.
It contains the same functions, even if a function with a single variable assignment in it is not very useful.
<syntaxhighlight lang="groovy">
def makeSwap (list, element1, element2) {
//exchanges two elements in a list.
//print a dot for each swap.
print "."
list[[element2,element1]] = list[[element1,element2]]
}▼
def checkSwap
//check if parent is smaller than child, then swap.
if (list[parent] < list[child]) makeSwap(list, child, parent)
}
def siftDown
//end represents the limit of how far down the heap to sift
def p = start▼
while (parent*2 < end)
//find the child with the higher value
//if the child has a sibling and the child's value is less than its sibling's..
if (child + 1 <= end && list[child] < list[child+1]) child++ //point to the other child
if (checkSwap(list, child, parent)) { //check if parent is smaller than child and swap
parent = child //make child to next parent
} else {
return //The rest of the heap is in order - return.
}
}
}
def heapify
// Create a heap out of a list
// run through all the heap parents and
// ensure that each parent is lager than the child for all parent/childs.
// (list.size() -2) / 2 = last parent in the heap.
for (start in ((list.size()-2).intdiv(2))..0 ) {
siftDown(list, start, list.size() - 1)
}
}
def heapSort
heapify(list) //ensure that the list is in a binary heap state
//Run the
//for end =
for (end in (list.size()-1)..0 ) {
makeSwap(list, 0, end) //put the top of the heap to the end (largest element)
siftDown(list, 0, end-1) //ensure that the rest is a heap again
}
list
}</syntaxhighlight>▼
▲}
▲</syntaxhighlight>
Test:
<syntaxhighlight lang="groovy">println (heapSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]))
Line 2,980 ⟶ 3,008:
toList (Node x l r) = x : toList (merge l r)
e.g
Line 5,558 ⟶ 5,586:
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func sift_down(a, start, end) {
var root = start
while ((2*root + 1) <= end) {
var child = (2*root + 1)
if ((child+1 <= end) && (a[child] < a[child + 1])) {
child += 1
}
if (a[root] < a[child]) {
a[child, root] = a[root, child]
root = child
} else {
return
}
}
}
func heapify(a, count) {
var start = ((count - 2) / 2)
while (start >= 0) {
sift_down(a, start, count-1)
start -= 1
}
}
func heap_sort(a, count) {
heapify(a, count)
var end = (count - 1)
while (end > 0) {
a[0, end] = a[end, 0]
end -= 1
sift_down(a, 0, end)
}
Line 5,592 ⟶ 5,620:
}
var arr = (1..10 -> shuffle)
say arr
heap_sort(arr, arr.len)
say arr
{{out}}
<pre>[10, 5, 2, 1, 7, 6, 4, 8, 3, 9]
Line 6,192 ⟶ 6,220:
=={{header|Wren}}==
<syntaxhighlight lang="
var root = start
while (root*2 + 1 <= end) {
Line 6,229 ⟶ 6,257:
}
var
for (a in
System.print("Before: %(a)")
heapSort.call(a)
Line 6,248 ⟶ 6,276:
Alternatively, we can just call a library method.
{{libheader|Wren-sort}}
<syntaxhighlight lang="
var
for (a in
System.print("Before: %(a)")
Sort.heap(a)
| |||