Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,718: / Line 2,718: @@
 =={{header|Javascript}}==
-{{trans|CoffeeScript}}
 <lang Javascript>
-function swap(data, i, j) {
+function heapSort(arr) {
+    heapify(arr)
-    var tmp = data[i];
-    data[i] = data[j];
+    end = arr.length - 1
-    data[j] = tmp;
+    while (end > 0) {
+        [arr[end], arr[0]] = [arr[0], arr[end]]
-}
+        end--
+        siftDown(arr, 0, end)
- function heap_sort(arr) {
-    put_array_in_heap_order(arr);
-    var end = arr.length - 1;
-    while(end > 0) {
-        swap(arr, 0, end);
-        sift_element_down_heap(arr, 0, end);
-        end -= 1
     }
 }
-function put_array_in_heap_order(arr) {
+function heapify(arr) {
+    start = Math.floor(arr.length/2) - 1
-    var i;
-    i = arr.length / 2 - 1;
-    i = Math.floor(i);
+    while (start >= 0) {
+        siftDown(arr, start, arr.length - 1)
-    while (i >= 0) {
+        start--
-        sift_element_down_heap(arr, i, arr.length);
-        i -= 1;
     }
 }
-function sift_element_down_heap(heap, i, max) {
+function siftDown(arr, startPos, endPos) {
-    var i_big, c1, c2;
+    let rootPos = startPos
-    while(i < max) {
-        i_big = i;
+    while (rootPos * 2 + 1 <= endPos) {
-        c1 = 2*i + 1;
+        childPos = rootPos * 2 + 1
-        c2 = c1 + 1;
+        if (childPos + 1 <= endPos && arr[childPos] < arr[childPos + 1]) {
-        if (c1 < max && heap[c1] > heap[i_big])
+            childPos++
-            i_big = c1;
+        }
-        if (c2 < max && heap[c2] > heap[i_big])
+        if (arr[rootPos] < arr[childPos]) {
-            i_big = c2;
+            [arr[rootPos], arr[childPos]] = [arr[childPos], arr[rootPos]]
-        if (i_big == i) return;
+            rootPos = childPos
-        swap(heap,i, i_big);
+        } else {
-        i = i_big;
+            return
+        }
     }
 }
+test('rosettacode', () => {
-arr = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8,];
+    arr = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8,]
-heap_sort(arr);
+    heapSort(arr)
+    expect(arr).toStrictEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
-alert(arr);</lang>
+})</lang>
 {{out}}
 <pre>