Rosetta Code

Sorting algorithms/Heapsort: Difference between revisions

Page Discussion

Sorting algorithms/Heapsort (view source)

Revision as of 11:50, 8 February 2024

1,214 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
imported>SerErris
(The code was completely unreadable for anyone want to find out what Heapsort does and how it works in groovy. This code should be much better to read. It is a adaption of the same code in JAVA example here.)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(9 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(makeSwap = { a, count){i, j = i+1 -> print "."; a[[j,i]] = a[[i,j]] }
//start is assigned the index in a of the last parent node
def start = (count - 2).intdiv(2) //binary heap
 
def checkSwap = { list, i, j = i+1 -> [(list[i] > list[j])].find{ it }.each { makeSwap(list, i, j) } }
while(start >= 0){
 
//sift down the node at index start to the proper place
def siftDown = { a, start, end ->
//such that all nodes below the start index are in heap
def p = //orderstart
while siftDown(a,p*2 start,< countend) - 1){
def c = p*2 + ((p*2 + 1 < end && a[p*2 + 2] > a[p*2 + 1]) ? 2 : 1)
start--
if (checkSwap(a, c, p)) { p = c }
else { return }
}
//after sifting down the root all nodes/elements are in heap order
}
 
def siftDown(a,heapify start,= end){
(((it.size()-2).intdiv(2))..0).each { start -> siftDown(it, start, it.size()-1) }
//end represents the limit of how far down the heap to sift
}
def root = start;
 
def heapSort = { list ->
while((root * 2 + 1) <= end){ //While the root has at least one child
heapify(list)
int child = root * 2 + 1 //root*2+1 points to the left child
(0..<(list.size())).reverse().each { end ->
//if the child has a sibling and the child's value is less than its sibling's...
ifmakeSwap(childlist, + 1 <=0, end && a[child] < a[child + 1])
siftDown(list, 0, end-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;
}
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) {
def heapSort(a){
//check if parent is smaller than child, then swap.
def count = a.size()
if (list[parent] < list[child]) makeSwap(list, child, parent)
}
 
def siftDown (list, start, end) {
//first place a in max-heap order
//end represents the limit of how far down the heap to sift
heapify(a, count)
//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 end = countheapify -(list) 1{
// Create a heap out of a list
while(end > 0){
//swap therun root(maximumthrough value) ofall the heap withparents theand
// ensure that each parent is lager than the child for all parent/childs.
//last element of the heap
// (list.size() -2) / 2 = last parent in the heap.
def tmp = a[end]
for (start in ((list.size()-2).intdiv(2))..0 ) {
a[end] = a[0]
a[0]siftDown(list, =start, tmplist.size() - 1)
//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--
}
}
 
def heapSort (list) {
return a
//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 2,981 ⟶ 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,559 ⟶ 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,593 ⟶ 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,193 ⟶ 6,220:
 
=={{header|Wren}}==
<syntaxhighlight lang="ecmascriptwren">var siftDown = Fn.new { |a, start, end|
var root = start
while (root*2 + 1 <= end) {
Line 6,230 ⟶ 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,249 ⟶ 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/349781...349791"