Merge pull request mgechev#125 from mik-laj/master

mgechev · web-flow · commit 16214cd9742f · 2017-06-07T14:14:03.000-04:00
Add quick sort (functional variant)
diff --git a/src/sorting/quicksort-declarative.js b/src/sorting/quicksort-declarative.js
@@ -0,0 +1,68 @@
+(function (exports) {
+
+  'use strict';
+
+  function compare(a, b) {
+    return a - b;
+  }
+
+  /**
+   * Quicksort algorithm (declarative variant)
+   *
+   * @public
+   * @param {array} array Array which should be sorted.
+   * @return {array} Sorted array.
+   */
+  var quickSort = (function () {
+
+    /**
+     * Recursively calls itself.
+     *
+     * @private
+     * @param {array} array Array which should be processed
+     */
+    function quicksort(array, cmp) {
+      if (array.length < 1) {
+        return array;
+      }
+
+      const [x, ...rest] = array;
+
+      return [
+        ...quicksort(rest.filter(v => cmp(v, x) < 0), cmp),
+        x,
+        ...quicksort(rest.filter(v => cmp(v, x) >= 0), cmp)
+      ];
+    }
+
+
+    /**
+     * Quicksort algorithm. In this version of quicksort used
+     * declarative programming mechanisms.<br><br>
+     * Time complexity: O(N log(N)).
+     *
+     * @example
+     *
+     * var sort = require('path-to-algorithms/src' +
+     * '/sorting/quicksort-declarative').quickSort;
+     * console.log(sort([2, 5, 1, 0, 4])); // [ 0, 1, 2, 4, 5 ]
+     *
+     * @public
+     * @module sorting/quicksort-declarative
+     * @param {Array} array Input array.
+     * @param {Function} cmp Optional. A function that defines an
+     * alternative sort order. The function should return a negative,
+     * zero, or positive value, depending on the arguments.
+     * @return {Array} Sorted array.
+     */
+    return function (array, cmp) {
+      cmp = cmp || compare;
+      array = quicksort(array, cmp);
+      return array;
+    };
+
+  }());
+
+  exports.quickSort = quickSort;
+
+}(typeof exports === 'undefined' ? window : exports));
diff --git a/test/sorting/quicksort-declarative.spec.js b/test/sorting/quicksort-declarative.spec.js
@@ -0,0 +1,5 @@
+var sortTestCase = require('./sort.testcase.js');
+var quickSort =
+      require('../../src/sorting/quicksort-declarative.js').quickSort;
+
+sortTestCase(quickSort, 'Quick sort');
diff --git a/test/sorting/sort.testcase.js b/test/sorting/sort.testcase.js
@@ -39,7 +39,7 @@ module.exports = function (sort, algorithmName, options) {
           precision: 0
         });
       }
-      sort(array);
+      array = sort(array);
       for (var i = 0; i < array.length - 1; i += 1) {
         expect(array[i] <= array[i + 1]).toBeTruthy();
       }
@@ -53,7 +53,7 @@ module.exports = function (sort, algorithmName, options) {
         }
 
         var array = createRandomArray();
-        sort(array, comparator);
+        array = sort(array, comparator);
 
         for (var i = 0; i < array.length - 1; i += 1) {
           expect(array[i] >= array[i + 1]).toBeTruthy();

Original file line number	Diff line number	Diff line change
`@@ -39,7 +39,7 @@ module.exports = function (sort, algorithmName, options) {`
`39`	`39`	`precision: 0`
`40`	`40`	`});`
`41`	`41`	`}`
`42`		`- sort(array);`
	`42`	`+ array = sort(array);`
`43`	`43`	`for (var i = 0; i < array.length - 1; i += 1) {`
`44`	`44`	`expect(array[i] <= array[i + 1]).toBeTruthy();`
`45`	`45`	`}`
`@@ -53,7 +53,7 @@ module.exports = function (sort, algorithmName, options) {`
`53`	`53`	`}`
`54`	`54`
`55`	`55`	`var array = createRandomArray();`
`56`		`- sort(array, comparator);`
	`56`	`+ array = sort(array, comparator);`
`57`	`57`
`58`	`58`	`for (var i = 0; i < array.length - 1; i += 1) {`
`59`	`59`	`expect(array[i] >= array[i + 1]).toBeTruthy();`