Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,892: / Line 2,892: @@
 =={{header|Groovy}}==
+Loose translation of the pseudocode:
-Translated from JAVA code:
-<syntaxhighlight lang="groovy">def heapify(a, count){
+<syntaxhighlight lang="groovy">def makeSwap = { a, 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
-        //order
+    def p = start
-        siftDown(a, start, count - 1)
+    while (p*2 < end) {
+        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, start, end){
+def heapify = {
+    (((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;
-    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 heapSort = { list ->
-    def count = a.size()
+    heapify(list)
+    (0..<(list.size())).reverse().each { end ->
+        makeSwap(list, 0, end)
-    //first place a in max-heap order
-    heapify(a, count)
+        siftDown(list, 0, end-1)
-    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--
     }
+    list
-    return a
 }</syntaxhighlight>