Few more algorithms added...(two variations of insertion sort + binary search)

mgechev · mgechev · commit 4adf352b2de5 · 2012-11-18T21:38:02.000+02:00
diff --git a/src/searching/binary-search.js b/src/searching/binary-search.js
@@ -0,0 +1,31 @@
+var array = [5, 8, 53, 56, 123, 322, 400, 2356, 8000, 23333];
+
+function binarySearch(array, key) {
+    var middle = Math.round(array.length / 2),
+        left = 0,
+        right = array.length;
+    while (right >= left) {
+        if (array[middle] === key) {
+            return middle;
+        } else if (array[middle] > key) {
+            right = middle - 1;
+        } else {
+            left = middle + 1;
+        }
+        middle = Math.floor((left + right) / 2);
+    }
+    return -1;
+}
+
+console.log(array);
+console.log(5, binarySearch(array, 5));
+console.log(8, binarySearch(array, 8));
+console.log(53, binarySearch(array, 53));
+console.log(56, binarySearch(array, 56));
+console.log(123, binarySearch(array, 123));
+console.log(322, binarySearch(array, 322));
+console.log(400, binarySearch(array, 400));
+console.log(2356, binarySearch(array, 2356));
+console.log(8000, binarySearch(array, 8000));
+console.log(8001, binarySearch(array, 8001));
+console.log(23333, binarySearch(array, 23333));
diff --git a/src/searching/recursive-binary-search.js b/src/searching/recursive-binary-search.js
@@ -0,0 +1,30 @@
+var array = [5, 8, 53, 56, 123, 322, 400, 2356, 8000, 23333];
+
+function binarySearch(array, key) {
+    return recursiveBinarySearch(array, key, 0, array.length);
+}
+
+function recursiveBinarySearch(array, key, left, right) {
+    if (left > right)
+        return -1;
+    var middle = Math.floor((right + left) / 2);
+    if (array[middle] === key)
+        return middle;
+    else if (array[middle] > key) 
+        return recursiveBinarySearch(array, key, left, middle - 1);
+    else
+        return recursiveBinarySearch(array, key, middle + 1, right);
+}
+
+console.log(array);
+console.log(5, binarySearch(array, 5));
+console.log(8, binarySearch(array, 8));
+console.log(53, binarySearch(array, 53));
+console.log(56, binarySearch(array, 56));
+console.log(123, binarySearch(array, 123));
+console.log(322, binarySearch(array, 322));
+console.log(400, binarySearch(array, 400));
+console.log(2356, binarySearch(array, 2356));
+console.log(8000, binarySearch(array, 8000));
+console.log(8001, binarySearch(array, 8001));
+console.log(23333, binarySearch(array, 23333));
diff --git a/src/sorting/bubble-sort.js b/src/sorting/bubble-sort.js
@@ -0,0 +1,17 @@
+var array = [3,5,2,4,7,9,6,4,5];
+
+function bubbleSort(array) {
+    var temp;
+    for (var i = 0; i < array.length; i += 1) {
+        for (var j = i; j > 0; j -= 1) {
+            if (array[j] < array[j - 1]) {
+                temp = array[j];
+                array[j] = array[j - 1];
+                array[j - 1] = temp;
+            }
+        }
+    }
+    return array;
+}
+
+console.log(bubbleSort(array));
diff --git a/src/sorting/insertion-binary-sort.js b/src/sorting/insertion-binary-sort.js
@@ -0,0 +1,27 @@
+var array = [5,6,3,3,6,8,9,4,3];
+
+function insertionBinarySort(array) {
+    var current,
+        middle,
+        left,
+        right;
+    for (var i = 1; i < array.length; i += 1) {
+        current = array[i];
+        left = 0;
+        right = i;
+        middle = Math.floor((left + right) / 2);
+        while (left < right) {
+            if (array[middle] <= current) 
+                left = middle + 1;
+            else 
+                right = middle - 1;
+            middle = Math.floor((left + right) / 2);
+        }
+        for (var j = i; j > middle; j -= 1) 
+            array[j] = array[j - 1];
+        array[j] = current;
+    }
+    return array;
+}
+
+console.log(insertionBinarySort(array));
diff --git a/src/sorting/recursive-insertion-sort.js b/src/sorting/recursive-insertion-sort.js
@@ -0,0 +1,15 @@
+var array = [4,6,2,2,4,56,7,7,51,23,5,7];
+
+function recursiveInsertionSort(array, max) {
+    if (max <= 0)
+        return array;
+    if (max === undefined) 
+        max = array.length - 1;
+    recursiveInsertionSort(array, max - 1);
+    for (var i = max - 1, current = array[max]; i >= 0 && current < array[i]; i -= 1) 
+        array[i + 1] = array[i];
+    array[i + 1] = current;
+    return array;
+}
+
+console.log(recursiveInsertionSort(array));
