Anonymous user
Sorting algorithms/Heapsort: Difference between revisions
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.
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.) |
|||
Line 2,892:
=={{header|Groovy}}==
Translated from JAVA code:
<syntaxhighlight lang="groovy">def
//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
start--
def c = p*2 + ((p*2 + 1 < end && a[p*2 + 2] > a[p*2 + 1]) ? 2 : 1)▼
else { return }▼
}
//after sifting down the root all nodes/elements are in heap order
}
def
//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...
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
}
def heapSort
//first place a in max-heap order
makeSwap(list, 0, end)▼
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
//decrement the size of the heap so that the previous
//max value will stay in its proper place
end--
}
▲ list
return a
}</syntaxhighlight>
Test:
| |||