Added more implementations (JS) (egonSchiele#67)

kas-elvirov · egonSchiele · commit 0d5d0164ce28 · 2018-08-24T11:21:54.000-07:00
* Added recursive binary search (JS) * Added recursive selection sorting * Added another loop implementation sum func by reduce (JS) * Recursion reduced by one iteration * Recursive binary search in ES6 added to appropriate folder * JS files ordered by standards (ES4/ES6) * Added hashtable implementation in JS * Fixed typo with LENGTH prop * Added Euclidian algorithm for two numbers and set of them * Added universal selection sort * Commented output * Added ES6 version of Euclidean algorithm * Converted from ES6 to ES5 * egonSchiele#69 Added search for LCS * egonSchiele#69 added levenstein algorithm * Removed excessive property * Removed excessive file * Removed excessive function calls * Removed excessive file * Removed excessive file * Renamed * Fixed indentation
diff --git a/01_introduction_to_algorithms/ES6/02_recursive_binary_search.js b/01_introduction_to_algorithms/ES6/02_recursive_binary_search.js
@@ -0,0 +1,43 @@
+/**
+ * Searches recursively number from the list
+ * @param {Array} list
+ * @param {number} item Search item
+ * @param {number} low Lower limit of search in the list
+ * @param {number} high Highest limit of search in the list
+ * @return {(number | null)} Number if the value is found or NULL otherwise
+ */
+const binarySearch = ( list, item, low, high ) => {
+    let arrLength = list.length;
+    while ( low <= high ) {
+        let mid = Math.floor((low + high) / 2);
+        let guess = list[mid];
+
+        if ( guess === item ) {
+            return mid;
+        } else if ( guess > item ) {
+            high = mid - 1;
+            list = list.slice( 0, mid );
+            return binarySearch( list, item, low, high );
+        } else {
+            low = mid + 1;
+            list = list.slice( low, arrLength );
+            return binarySearch( list, item, low, high );
+        }
+    }
+
+    return null;
+};
+
+/**
+ * Creates the array that contains numbers 1...N
+ * @param {number} n - number N
+ * @return {Array}
+ */
+const createArr = ( n ) => Array.from({length: n}, (v, k) => k + 1);
+
+const myList = createArr( 100 );
+let low = 0;
+let high = myList.length - 1;
+
+console.log( binarySearch( myList, 3, low, high ) ); // 2
+console.log( binarySearch( myList, -1, low, high ) ); // null
diff --git a/02_selection_sort/javascript/02_recursive_selection_sort.js b/02_selection_sort/javascript/02_recursive_selection_sort.js
@@ -0,0 +1,33 @@
+/**
+ * Finds smallest element of an aray
+ * @param {Array} arr array for searching
+ * @return {number} index of the smallest element in array
+ */
+const findSmallest = ( arr ) => {
+    let smallest = arr[0];
+    let smallestIndex = 0;
+    let arrLen = arr.length;
+
+    for ( let i = 0; i < arrLen; i++ ) {
+        if ( arr[i] < smallest ) {
+            smallest = arr[i];
+            smallestIndex = i;
+        }
+    }
+    return smallestIndex;
+};
+
+/**
+ * Sorts0 recursively an array of numbers
+ * @param {Array} arr An array of numbers
+ * @return {Array} New sorted array
+ */
+const selectionSort = ( arr ) => {
+    if ( !arr.length ) return [];
+    let smallest = arr.splice( findSmallest( arr ), 1 );
+    return smallest.concat( selectionSort( arr ) );
+};
+
+let arr = [5, 3, 6, 2, 10];
+
+console.log( selectionSort(arr) );
diff --git a/04_quicksort/ES6/01_loop_sum.js b/04_quicksort/ES6/01_loop_sum.js
@@ -1,9 +1,18 @@
-const sum = (arr) => {
-  let total = 0;
-  for (let x = 0; x < arr.length; x += 1) {
-    total += arr[x];
-  }
-  return total;
+/**
+ * Sums values in array by loop "for"
+ * @param {Array} arr Array of numbers
+ * @return {number} Sum of the numbers
+ */
+const sumLoop = ( arr ) => {
+    let result = 0;
+
+    for ( let i = 0; i < newArr.length; i++ ) {
+        result += newArr[i];
+    }
+
+    return result;
 };
 
-console.log(sum([1, 2, 3, 4])); // 10
+let arr = [1, 2, 3, 4];
+
+console.log( sumLoop( arr ) ); // 10
diff --git a/04_quicksort/ES6/01_loop_sum_reduce_version.js b/04_quicksort/ES6/01_loop_sum_reduce_version.js
@@ -0,0 +1,16 @@
+/**
+ * Sums values in array by function "reduce"
+ * @param {Array} arr Array of numbers
+ * @return {number} Sum of the numbers
+ */
+const sumReduce = ( arr ) => {
+    let result = newArr.reduce( ( curr, prev ) => {
+        return curr + prev;
+    } );
+
+    return result;
+};
+
+let arr = [1, 2, 3, 4];
+
+console.log( sumReduce( arr ) ); // 10
diff --git a/04_quicksort/ES6/06_euclidean_algorithm_set_numbers.js b/04_quicksort/ES6/06_euclidean_algorithm_set_numbers.js
@@ -0,0 +1,36 @@
+/**
+ * Recursive function of Euclidean algorithm for two numbers
+ *
+ * @param {number} a first number
+ * @param {number} b second number (base case)
+ *
+ * @return {number} GCD (greatest common divisor)
+ */
+let gcdOfTwo = ( a, b ) => {
+    if ( !b ) {
+        return a;
+    }
+    return gcdOfTwo( b, a % b );
+};
+
+/**
+ * Recursive function of Euclidean algorithm for set of the numbers
+ *
+ * @param {Array} set Set of the numbers
+ *
+ * @return {number} GCD (greatest common divisor)
+ */
+let gcdOfSet = ( set ) => {
+    let result = set[0];
+    let newArr = Array.prototype.slice.call( set, 1 );
+
+    newArr.map( ( el ) => {
+        result = gcdOfTwo( result, el );
+    } );
+
+    return result;
+};
+
+const set = [1680, 640, 3360, 160, 240, 168000];
+
+console.log( gcdOfSet( set ) ); // 80
diff --git a/04_quicksort/ES6/07_euclidean_algorithm_two_numbers.js b/04_quicksort/ES6/07_euclidean_algorithm_two_numbers.js
@@ -0,0 +1,19 @@
+/**
+ * Recursive function of Euclidean algorithm
+ *
+ * @param {number} a first number
+ * @param {number} b second number (base case)
+ *
+ * @return {number} GCD (greatest common divisor)
+ */
+let getGCD = ( a, b ) => {
+    if ( !b ) {
+        return a;
+    }
+    return getGCD( b, a % b );
+};
+
+const a = 1680;
+const b = 640;
+
+console.log( getGCD( a, b ) ); // 80
diff --git a/04_quicksort/javascript/01_loop_sum.js b/04_quicksort/javascript/01_loop_sum.js
@@ -1,11 +1,18 @@
-'use strict';
-
-function sum(arr) {
-  let total = 0;
-  for (let x = 0; x < arr.length; x++) {
-    total += arr[x];
-  }
-  return total;
+/**
+ * Sums values in array by loop "for"
+ * @param {Array} arr Array of numbers
+ * @return {number} Sum of the numbers
+ */
+function sumLoop( arr ) {
+    var result = 0;
+
+    for ( var i = 0; i < newArr.length; i++ ) {
+        result += newArr[i];
+    }
+
+    return result;
 }
 
-console.log(sum([1, 2, 3, 4])) // 10
+var arr = [1, 2, 3, 4];
+
+console.log( sumLoop( arr ) ); // 10
diff --git a/04_quicksort/javascript/01_loop_sum_reduce_version.js b/04_quicksort/javascript/01_loop_sum_reduce_version.js
@@ -0,0 +1,16 @@
+/**
+ * Sums values in array by function "reduce"
+ * @param {Array} arr Array of numbers
+ * @return {number} Sum of the numbers
+ */
+function sumReduce( arr ) {
+    var result = newArr.reduce( ( curr, prev ) => {
+        return curr + prev;
+    } );
+
+    return result;
+}
+
+var arr = [1, 2, 3, 4];
+
+console.log( sumReduce( arr ) ); // 10
diff --git a/04_quicksort/javascript/02_recursive_sum.js b/04_quicksort/javascript/02_recursive_sum.js
@@ -1,10 +1,13 @@
-'use strict';
+const arr = [1, 2, 3, 4];
 
-function sum(list) {
-  if (list.length === 0) {
-    return 0;
-  }
-  return list[0] + sum(list.slice(1));
-}
+/**
+ * Sums values in array recursively
+ * @param {Array} arr Array of numbers
+ * @return {number} Sum of the numbers
+ */
+const sumRecursive = ( arr ) => {
+    if ( arr.length == 1 ) return arr[0];
+    return arr[0] + sumRecursive( arr.slice( 1 ) );
+};
 
-console.log(sum([1, 2, 3, 4])) // 10
+console.log( sumRecursive( arr ) );  // 10
diff --git a/05_hash_tables/javascript/03_hashtable.js b/05_hash_tables/javascript/03_hashtable.js
diff --git a/09_dynamic_programming/javascript/01_longest_common_subsequence.js b/09_dynamic_programming/javascript/01_longest_common_subsequence.js
diff --git a/09_dynamic_programming/javascript/02_levenstein.js b/09_dynamic_programming/javascript/02_levenstein.js
