Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,892: / Line 2,892: @@
 =={{header|Groovy}}==
+Translated from JAVA code:
-Loose translation of the pseudocode:
-<syntaxhighlight lang="groovy">def makeSwap = { a, i, j = i+1 -> print "."; a[[j,i]] = a[[i,j]] }
+<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){
-def checkSwap = { list, i, j = i+1 -> [(list[i] > list[j])].find{ it }.each { makeSwap(list, i, j) } }
+        //sift down the node at index start to the proper place
+        //such that all nodes below the start index are in heap
-def siftDown = { a, start, end ->
-    def p = start
+        //order
-    while (p*2 < end) {
+        siftDown(a, start, count - 1)
+        start--
-        def c = p*2 + ((p*2 + 1 < end && a[p*2 + 2] > a[p*2 + 1]) ? 2 : 1)
-        if (checkSwap(a, c, p)) { p = c }
-        else                    { return }
     }
+    //after sifting down the root all nodes/elements are in heap order
 }
-def heapify = {
+def siftDown(a, start, end){
+    //end represents the limit of how far down the heap to sift
-    (((it.size()-2).intdiv(2))..0).each { start -> siftDown(it, start, it.size()-1) }
+    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 = { list ->
+def heapSort(a){
-    heapify(list)
+    def count = a.size()
-    (0..<(list.size())).reverse().each { end ->
+    //first place a in max-heap order
-        makeSwap(list, 0, end)
-        siftDown(list, 0, end-1)
+    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--
     }
-    list
+    return a
 }</syntaxhighlight>
 Test: