Merge pull request AllAlgorithms#25 from Ditobaskoro/flashSort

abranhe · web-flow · commit 4eaf01b1f09f · 2018-10-02T18:31:17.000-04:00
create flashSort
diff --git a/sorting/flashSort.js b/sorting/flashSort.js
@@ -0,0 +1,83 @@
+// JavaScript implementation of flash sort
+// Flashsort is a distribution sorting algorithm showing linear computational complexity O(n)
+//
+// Author: Dito Baskoro
+
+function flash_sort(arr) 
+  {
+    let max = 0, min = arr[0];
+    let n = arr.length;
+    let m = ~~(0.45 * n);
+    let l = new Array(m);
+ 
+    for (let i = 1; i < n; ++i) {
+        if (arr[i] < min) {
+            min = arr[i];
+        }
+        if (arr[i] > arr[max]) {
+            max = i;
+        }
+    }
+ 
+     if (min === arr[max]) {
+        return arr;
+    }
+ 
+    let c1 = (m - 1) / (arr[max] - min);
+ 
+ 
+    for (let k = 0; k < m; k++) {
+        l[k] = 0;
+    }
+    for (let j = 0; j < n; ++j) {
+        k = ~~(c1 * (arr[j] - min));
+        ++l[k];
+    }
+ 
+    for (let p = 1; p < m; ++p) {
+        l[p] = l[p] + l[p - 1];
+    }
+ 
+    let hold = arr[max];
+    arr[max] = arr[0];
+    arr[0] = hold;
+ 
+    //permutation
+    let move = 0, t, flash;
+    j = 0; 
+    k = m - 1;
+  
+    while (move < (n - 1)) {
+        while (j > (l[k] - 1)) {
+            ++j;
+            k = ~~(c1 * (arr[j] - min));
+        }
+        if (k < 0) break;
+        flash = arr[j];
+        while (j !== l[k]) {
+            k = ~~(c1 * (flash - min));
+            hold = arr[t = --l[k]];
+            arr[t] = flash;
+            flash = hold;
+            ++move;
+        }
+    }
+ 
+    //insertion
+    for (j = 1; j < n; j++) {
+        hold = arr[j];
+         i = j - 1;
+        while (i >= 0 && arr[i] > hold) {
+            arr[i + 1] = arr[i--];
+        }
+        arr[i + 1] = hold;
+    }
+    return arr;
+}
+
+//test
+const array = [3, 0, 2, 5, -1, 4, 1, -2]; 
+console.log("Original Array"); 
+console.log(array); 
+console.log("Sorted Array"); 
+console.log(flash_sort(array, 0, 5));
