Merge pull request #15 from Ditobaskoro/heapSort

abranhe · web-flow · commit 68ad56eb0da5 · 2018-10-02T00:51:39.000-04:00
Create Heap sort
diff --git a/sorting/heapSort.js b/sorting/heapSort.js
@@ -0,0 +1,52 @@
+// JavaScript implementation of heap sort
+//
+// Author: Dito Baskoro
+
+let array_length;
+/* to create MAX  array */  
+function heap_root(input, i) {
+    let left = 2 * i + 1;
+    let right = 2 * i + 2;
+    let max = i;
+
+    if (left < array_length && input[left] > input[max]) {
+        max = left;
+    }
+
+    if (right < array_length && input[right] > input[max])     {
+        max = right;
+    }
+
+    if (max != i) {
+        swap(input, i, max);
+        heap_root(input, max);
+    }
+}
+
+function swap(input, index_A, index_B) {
+    let temp = input[index_A];
+
+    input[index_A] = input[index_B];
+    input[index_B] = temp;
+}
+
+function heapSort(input) {
+    
+    array_length = input.length;
+
+    for (let i = Math.floor(array_length / 2); i >= 0; i -= 1)      {
+        heap_root(input, i);
+      }
+
+    for (i = input.length - 1; i > 0; i--) {
+        swap(input, 0, i);
+        array_length--;
+      
+      
+        heap_root(input, 0);
+    }
+}
+
+const arr = [3, 0, 2, 5, -1, 4, 1, -2];
+heapSort(arr);
+console.log(arr);
