Rosetta Code

Sorting algorithms/Heapsort: Difference between revisions

Page Discussion

Sorting algorithms/Heapsort (view source)

Revision as of 11:50, 8 February 2024

368 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
imported>SerErris
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(8 intermediate revisions by 5 users not shown)
Line 2,251:
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
call sort data[]
print data[]
</syntaxhighlight>
Line 2,892:
 
=={{header|Groovy}}==
Loose translation of the pseudocode:
Translated from JAVA code:
<syntaxhighlight lang="groovy">def heapify(a, count){
//start is assigned the index in a of the last parent node
def start = (count - 2).intdiv(2) //binary heap
 
while(start >= 0){
//sift down the node at index start to the proper place
//such that all nodes below the start index are in heap
//order
siftDown(a, start, count - 1)
start--
}
//after sifting down the root all nodes/elements are in heap order
}
 
def siftDown(a, start, end){
//end represents the limit of how far down the heap to sift
def root = start;
 
while((root * 2 + 1) <= end){ //While the root has at least one child
int child = root * 2 + 1 //root*2+1 points to the left child
//if the child has a sibling and the child's value is less than its sibling's...
if(child + 1 <= end && a[child] < a[child + 1])
child = child + 1 //... then point to the right child instead
if(a[root] < a[child]){ //out of max-heap order
int tmp = a[root] //exchange root and child
a[root] = a[child]
a[child] = tmp
root = child //repeat to continue sifting down the child now
}else
return;
}
}
 
def heapSort(a){
def count = a.size()
 
//first place a in max-heap order
heapify(a, count)
 
def end = count - 1
while(end > 0){
//swap the root(maximum value) of the heap with the
//last element of the heap
def tmp = a[end]
a[end] = a[0]
a[0] = tmp
//put the heap back in max-heap order
siftDown(a, 0, end - 1)
//decrement the size of the heap so that the previous
//max value will stay in its proper place
end--
}
 
return a
}</syntaxhighlight>
 
This was the old code before if you are interested in how to code it in the most unreadable form:
 
<syntaxhighlight lang="groovy">def makeSwap = { a, i, j = i+1 -> print "."; a[[j,i]] = a[[i,j]] }
 
Line 2,975 ⟶ 2,917:
}
list
}</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 (list, child, parent) {
//check if parent is smaller than child, then swap.
if (list[parent] < list[child]) makeSwap(list, child, parent)
}
 
</syntaxhighlight>
def siftDown (list, start, end) {
//end represents the limit of how far down the heap to sift
//start is the head of the heap
def parent = start
while (parent*2 < end) { //While the root has at least one child
def child = parent*2 + 1 //root*2+1 points to the left child
//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 (list) {
// 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 (list) {
//heap sort any unsorted list
heapify(list) //ensure that the list is in a binary heap state
//Run the list backwards and
//for end = (size of list -1 ) to 0
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>
 
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 3,010 ⟶ 3,008:
toList (Node x l r) = x : toList (merge l r)
 
mergeSortheapSort :: Ord a => [a] -> [a]
mergeSortheapSort = toList . fromList</syntaxhighlight>
 
e.g
Line 5,588 ⟶ 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; nil
}
}
}
 
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,622 ⟶ 5,620:
}
 
var arr = (1..10 -> shuffle); # creates a shuffled array
say arr; # prints the unsorted array
heap_sort(arr, arr.len); # sorts the array in-place
say arr; # prints the sorted array</syntaxhighlight>
{{out}}
<pre>[10, 5, 2, 1, 7, 6, 4, 8, 3, 9]
Line 6,222 ⟶ 6,220:
 
=={{header|Wren}}==
<syntaxhighlight lang="ecmascriptwren">var siftDown = Fn.new { |a, start, end|
var root = start
while (root*2 + 1 <= end) {
Line 6,259 ⟶ 6,257:
}
 
var asarray = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
for (a in asarray) {
System.print("Before: %(a)")
heapSort.call(a)
Line 6,278 ⟶ 6,276:
Alternatively, we can just call a library method.
{{libheader|Wren-sort}}
<syntaxhighlight lang="ecmascriptwren">import "./sort" for Sort
 
var asarray = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
for (a in asarray) {
System.print("Before: %(a)")
Sort.heap(a)
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/349782...349791"