js-sorting - npm Package Compare versions

Comparing version 1.2.0 to 2.0.0

bower.json

 {
   "name": "js-sorting",
-  "version": "1.2.0",
+  "version": "2.0.0",
   "homepage": "https://github.com/Tyriar/js-sorting",
@@ -16,7 +16,6 @@ "authors": [
     "algorithm",
-    "computer",
-    "science",
+    "computer science",
     "sorting"
   ],
-  "license": "BSD-2-clause",
+  "license": "MIT",
   "ignore": [
@@ -23,0 +22,0 @@ "**/.*",

package.json

 {
   "name": "js-sorting",
-  "version": "1.2.0",
+  "version": "2.0.0",
   "description": "A collection of sorting algorithms written in JavaScript.",
-  "devDependencies": {
-    "jasmine-node": "~1.14.3"
-  },
   "scripts": {
@@ -21,7 +18,16 @@ "test": "jasmine-node ."
   "author": "Daniel Imms (http://www.growingwiththeweb.com)",
-  "license": "BSD-2-Clause",
+  "license": "MIT",
   "bugs": {
     "url": "https://github.com/Tyriar/js-sorting/issues"
   },
-  "homepage": "https://github.com/Tyriar/js-sorting"
+  "homepage": "https://github.com/Tyriar/js-sorting",
+  "devDependencies": {
+    "grunt": "^0.4.5",
+    "grunt-contrib-clean": "^0.5.0",
+    "grunt-contrib-copy": "^0.5.0",
+    "grunt-contrib-uglify": "^0.5.0",
+    "grunt-jasmine-node-coverage": "^0.1.11",
+    "jasmine-node": "~1.14.3",
+    "jasmine-reporters": ">=0.2.0 <2.0.0"
+  }
 }

README.md

 # js-sorting
 
-[![Build Status](https://secure.travis-ci.org/Tyriar/js-sorting.png)](http://travis-ci.org/Tyriar/js-sorting)
+[![NPM version](http://img.shields.io/npm/v/js-sorting.svg?style=flat)](https://www.npmjs.org/package/js-sorting)
+[![Build Status](http://img.shields.io/travis/Tyriar/js-sorting.svg?style=flat)](http://travis-ci.org/Tyriar/js-sorting)
+[![Code climate](http://img.shields.io/codeclimate/github/Tyriar/js-sorting.svg?style=flat)](https://codeclimate.com/github/Tyriar/js-sorting)
+[![Code coverage](http://img.shields.io/codeclimate/coverage/github/Tyriar/js-sorting.svg?style=flat)](https://codeclimate.com/github/Tyriar/js-sorting)
 
-A collection of sorting algorithms written in JavaScript. Each algorithm is enclosed in its own file wrapped in a [Universal Module Definition (UMD)][1] API to make it easier to use across multiple platforms.
+A collection of sorting algorithms written in JavaScript. Each algorithm is enclosed in its own file, wrapped in a [Universal Module Definition (UMD)][1] API to make it easier to use across multiple platforms.
 
-To learn more about how each algorithm is implemented have a look at the [technical articles on my blog][2].
+Detailed information on the complexity of each algorithm is located [here][6]. To learn more about how some of the algorithms are implemented, have a look at the [technical articles on my blog][2].
 
+## Installing
+
+```
+# via bower
+bower install --save js-sorting
+
+# via NPM
+npm install --save js-sorting
+```
+
+## Including
+
+**Browser**
+
+```html
+<script src="bower_components/js-sorting/src/merge-sort.js"></script>
+```
+
+**Node.JS**
+
+```javascript
+var mergeSort = require("merge-sort");
+```
+
+## Usage
+
+See [the source files][4] for a list sorts available and their public interfaces, Here is an example for the [merge sort][5].
+
+```javascript
+// Sort normally
+mergeSort.sort([5, 3, 2, 4, 1]);
+
+// Sort in reverse
+mergeSort.compare = function (a, b) {
+    return b - a;
+};
+mergeSort.sort([5, 3, 2, 4, 1]);
+
+// Sort complex objects
+var list = [
+  { 'firstname': 'John',   'lastname': 'Smith'   },
+  { 'firstname': 'Daniel', 'lastname': 'Imms'    },
+  { 'firstname': 'Mary',   'lastname': 'Jackson' },
+  { 'firstname': 'John',   'lastname': 'Brown'   },
+  { 'firstname': 'Mary',   'lastname': 'Harris'  },
+];
+mergeSort.compare = function (a, b) {
+  // Sort by first name first
+  if (a.firstname.toLowerCase() < b.firstname.toLowerCase()) return -1;
+  if (a.firstname.toLowerCase() > b.firstname.toLowerCase()) return 1;
+  // Sort by last name second
+  if (a.lastname.toLowerCase() < b.lastname.toLowerCase()) return -1;
+  if (a.lastname.toLowerCase() > b.lastname.toLowerCase()) return 1;
+  return 0;
+};
+mergeSort.sort(list);
+```
+
+### Observing array changes
+
+In order to support [one of my other projects][8], various methods are exposed for each sort that allow observation of internal array changes. This can be done by wrapping the functions like so:
+
+```javascript
+var originalCompare = bubbleSort.compare;
+bubbleSort.compare = function (a, b) {
+  alert('Comparing value at index "' + a + '" with "' + b + '"');
+  originalCompare(array, a, b);
+};
+
+var originalSwap = bubbleSort.swap;
+bubbleSort.swap = function (array, a, b) {
+  alert('Swapping "' + array[a] + '" (i=' + a + ') with "' +
+                       array[b] + '" (i=' + b + ')');
+  originalSwap(array, a, b);
+};
+```
+
+The functions available are different for each algorithm since not all sorts only do compares and swaps to transform the array in a standard way. For example [insertion sort exposes a `shift` function][9] which shifts an item to a particular index. While this is the same as swapping the item with the adjacent item until it reaches the index, it is achieved in half the number of assignments by only assigning the item being shifted once. The way that this operation is visualised is quite different to just x swaps.
+
 ## Contributing
@@ -13,13 +95,30 @@
 
-## Testing locally
+### Testing locally
 
-    npm install
-    npm test
+```
+npm install
+npm test
 
+# generate coverage report in ./coverage/
+grunt coverage
+```
+
 ## License
 
-js-sorting is released under [BSD (2 clause)][3].
+MIT © [Daniel Imms][7]
 
-[1]: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
-[2]: http://www.growingwiththeweb.com/p/explore.html?t=Sorting
-[3]: https://github.com/Tyriar/js-sorting/blob/master/LICENSE
+## See also
+
+* [Tyriar/js-data-structures][3]
+
+
+
+  [1]: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
+  [2]: http://www.growingwiththeweb.com/p/explore.html?t=Sorting
+  [3]: https://github.com/Tyriar/js-data-structures
+  [4]: https://github.com/Tyriar/js-sorting/tree/master/src
+  [5]: https://github.com/Tyriar/js-sorting/blob/master/src/merge-sort.js
+  [6]: https://github.com/Tyriar/js-sorting/blob/master/src/README.md
+  [7]: http://www.growingwiththeweb.com
+  [8]: https://github.com/Tyriar/sorting-visualiser
+  [9]: https://github.com/Tyriar/js-sorting/blob/master/src/insertion-sort.js

src/bubble-sort.js

@@ -1,10 +0,1 @@
-// Explanation: http://www.growingwiththeweb.com/2014/02/bubble-sort.html
-//
-// Complexity (n=input size):
-//   Time, worse case:   O(n^2)
-//   Time, best case:    O(n^2)
-//   Time, average case: O(n^2)
-//   Space worst case:   O(1) auxiliary
-
-// UMD pattern: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
 (function (root, factory) {
@@ -21,37 +12,43 @@ 'use strict';
   }
-}(this, function (assert) {
+}(this, function () {
   'use strict';
 
-  var bubbleSort = {
-    sort: sort
-  };
+  var algorithm = {
 
-  function sort(array, compareFunc) {
-    var i, j;
-    
-    for (i = 0; i < array.length - 1; i++) {
-      for (j = 1; j < array.length - i; j++) {
-        if (compare(array[j - 1], array[j], compareFunc) > 0) {
-          swap(array, j, j - 1);
+    sort: function (array) {
+      var i, j;
+
+      for (i = 0; i < array.length - 1; i++) {
+        for (j = 1; j < array.length - i; j++) {
+          if (algorithm.compare(array[j - 1], array[j]) > 0) {
+            algorithm.swap(array, j, j - 1);
+          }
         }
       }
-    }
 
-    return array;
-  }
+      return array;
+    },
 
-  function swap(array, a, b) {
-    var temp = array[a];
-    array[a] = array[b];
-    array[b] = temp;
-  }
+    // Swaps elements at indexes `a` and `b`.
+    swap: function (array, a, b) {
+      var temp = array[a];
+      array[a] = array[b];
+      array[b] = temp;
+    },
 
-  function compare(a, b, compareFunc) {
-    if (compareFunc) {
-      return compareFunc(a, b);
+    // Compares elements at indexes `a` and `b`. Returns 0 if they're equal, a
+    // positive number if `a` is larger or a negative number if `b` is larger.
+    compare: function (a, b) {
+      if (a > b) {
+        return 1;
+      }
+      if (a < b) {
+        return -1;
+      }
+      return 0;
     }
-    return a - b;
-  }
 
-  return bubbleSort;
+  };
+
+  return algorithm;
 }));

src/counting-sort.js

@@ -1,10 +0,1 @@
-// Explanation: http://www.growingwiththeweb.com/2014/05/counting-sort.html
-//
-// Complexity (n=input size, k=possible number of values)
-//   Time, worse case:   O(n + k)
-//   Time, best case:    O(n + k)
-//   Time, average case: O(n + k)
-//   Space worst case:   O(n + k) auxiliary
-
-// UMD pattern: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
 (function (root, factory) {
@@ -21,23 +12,23 @@ 'use strict';
   }
-}(this, function (assert) {
+}(this, function () {
   'use strict';
 
-  var countingSort = {
-    sort: sort
-  };
+  var algorithm = {
 
-  // Routes function calls to the correct internal method, call like:
-  // sort(array, maxValue)
-  // sort(array, minValue, maxValue)
-  function sort() {
-    if (arguments.length === 2) {
-      return sortWithMax.apply(null, arguments);
+    // Routes function calls to the correct internal method, call like:
+    // sort(array, maxValue)
+    // sort(array, minValue, maxValue)
+    sort: function () {
+      if (arguments.length === 2) {
+        return sortWithMax.apply(null, arguments);
+      }
+      if (arguments.length === 3) {
+        return sortWithMinAndMax.apply(null, arguments);
+      }
+      throw 'Cannot sort with counting sort with ' + arguments.length +
+        ' arguments';
     }
-    if (arguments.length === 3) {
-      return sortWithMinAndMax.apply(null, arguments);
-    }
-    throw "Cannot sort with counting sort with " + arguments.length +
-      " arguments";
-  }
 
+  };
+
   function sortWithMax(array, maxValue) {
@@ -95,3 +86,3 @@ var buckets = new Array(maxValue + 1);
 
-  return countingSort;
+  return algorithm;
 }));

src/heapsort.js

@@ -1,10 +0,1 @@
-// Explanation: http://www.growingwiththeweb.com/2012/11/algorithm-heapsort.html
-//
-// Complexity (n=input size)
-//   Time, worse case:   O(n log n)
-//   Time, best case:    O(n log n)
-//   Time, average case: O(n log n)
-//   Space worst case:   O(1) auxiliary
-
-// UMD pattern: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
 (function (root, factory) {
@@ -21,26 +12,46 @@ 'use strict';
   }
-}(this, function (assert) {
+}(this, function () {
   'use strict';
 
-  var heapsort = {
-    sort: sort
+  var algorithm = {
+
+    sort: function (array) {
+      var heapSize = array.length;
+      buildHeap(array, heapSize);
+      while (heapSize > 1) {
+        algorithm.swap(array, 0, heapSize - 1);
+        heapSize--;
+        heapify(array, heapSize, 0);
+      }
+      return array;
+    },
+
+    // Swaps elements at indexes `a` and `b`.
+    swap: function (list, a, b) {
+      var temp = list[a];
+      list[a] = list[b];
+      list[b] = temp;
+    },
+
+    // Compares elements at indexes `a` and `b`. Returns 0 if they're equal, a
+    // positive number if `a` is larger or a negative number if `b` is larger.
+    compare: function (a, b) {
+      if (a > b) {
+        return 1;
+      }
+      if (a < b) {
+        return -1;
+      }
+      return 0;
+    }
+
   };
 
-  function sort(array, compareFunc) {
-    var heapSize = array.length;
-    buildHeap(array, heapSize, compareFunc);
-    while (heapSize > 1) {
-      swap(array, 0, heapSize - 1);
-      heapSize--;
-      heapify(array, heapSize, 0, compareFunc);
+  function buildHeap(array, heapSize) {
+    for (var i = Math.floor(array.length / 2); i >= 0; i--) {
+      heapify(array, heapSize, i);
     }
-    return array;
   }
 
-  function buildHeap(array, heapSize, compareFunc) {
-    for (var i = Math.floor(array.length / 2); i >= 0; i--)
-      heapify(array, heapSize, i, compareFunc);
-  }
-
-  function heapify(array, heapSize, i, compareFunc) {
+  function heapify(array, heapSize, i) {
     var left = i * 2 + 1;
@@ -51,3 +62,3 @@ var right = i * 2 + 2;
     if (left < heapSize &&
-        compare(array[left], array[i], compareFunc) > 0) {
+        algorithm.compare(array[left], array[i]) > 0) {
       largest = left;
@@ -59,26 +70,13 @@ } else {
     if (right < heapSize &&
-        compare(array[right], array[largest], compareFunc) > 0) {
+        algorithm.compare(array[right], array[largest]) > 0) {
       largest = right;
     }
 
-    if (largest != i) {
-      swap(array, i, largest);
-      heapify(array, heapSize, largest, compareFunc);
+    if (largest !== i) {
+      algorithm.swap(array, i, largest);
+      heapify(array, heapSize, largest);
     }
   }
 
-  function swap(list, a, b) {
-    var temp = list[a];
-    list[a] = list[b];
-    list[b] = temp;
-  }
-
-  function compare(a, b, compareFunc) {
-    if (compareFunc) {
-      return compareFunc(a, b);
-    }
-    return a - b;
-  }
-
-  return heapsort;
+  return algorithm;
 }));

src/insertion-sort.js

@@ -1,10 +0,1 @@
-// Explanation: http://www.growingwiththeweb.com/2012/11/algorithm-insertion-sort.html
-//
-// Complexity (n=input size)
-//   Time, worse case:   O(n^2)
-//   Time, best case:    O(n)
-//   Time, average case: O(n^2)
-//   Space worst case:   O(1) auxiliary
-
-// UMD pattern: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
 (function (root, factory) {
@@ -14,3 +5,3 @@ 'use strict';
     define([], function () {
-        return (root.insertionSort = factory());
+      return (root.insertionSort = factory());
     });
@@ -22,33 +13,46 @@ } else if (typeof exports === 'object') {
   }
-}(this, function (assert) {
+}(this, function () {
   'use strict';
 
-  var insertionSort = {
-    sort: sort
-  };
+  var algorithm = {
 
-  function sort(array, compareFunc) {
-    var i;
+    sort: function (array) {
+      var i;
 
-    for (i = 1; i < array.length; i++) {
-      var item = array[i];
-      var indexHole = i;
-      while (indexHole > 0 && 
-          compare(array[indexHole - 1], item, compareFunc) > 0) {
-        array[indexHole] = array[--indexHole];
+      for (i = 1; i < array.length; i++) {
+        var item = array[i];
+        var indexHole = i;
+        while (indexHole > 0 &&
+            algorithm.compare(array[indexHole - 1], item) > 0) {
+          array[indexHole] = array[--indexHole];
+        }
+        array[indexHole] = item;
+        algorithm.shift(i, indexHole);
       }
-      array[indexHole] = item;
-    }
 
-    return array;
-  }
+      return array;
+    },
 
-  function compare(a, b, compareFunc) {
-    if (compareFunc) {
-      return compareFunc(a, b);
+    // Called when an element is being shifted from index `from` to index `to`,
+    // swapping all elements in-between.
+    //
+    // Example:
+    // b, c, d, e, a -> shift(4, 0) -> a, b, c, d, e
+    shift: function (from, to) { },
+
+    // Compares elements at indexes `a` and `b`. Returns 0 if they're equal, a
+    // positive number if `a` is larger or a negative number if `b` is larger.
+    compare: function (a, b) {
+      if (a > b) {
+        return 1;
+      }
+      if (a < b) {
+        return -1;
+      }
+      return 0;
     }
-    return a - b;
-  }
 
-  return insertionSort;
+  };
+
+  return algorithm;
 }));

src/merge-sort-bottom-up.js

@@ -1,46 +0,51 @@
-// Explanation: http://www.growingwiththeweb.com/2012/11/algorithm-merge-sort.html
-//
-// Complexity (n=input size)
-//   Time, worse case:   O(n log n)
-//   Time, best case:    O(n log n)
-//   Time, average case: O(n log n)
-//   Space worst case:   O(n) auxiliary
-
-// UMD pattern: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
 (function (root, factory) {
   'use strict';
   if (typeof define === 'function' && define.amd) {
-  define([], function () {
-    return (root.mergeSortBottomUp = factory());
-  });
+    define([], function () {
+      return (root.mergeSortBottomUp = factory());
+    });
   } else if (typeof exports === 'object') {
-  module.exports = factory();
+    module.exports = factory();
   } else {
-  root.mergeSortBottomUp = factory();
+    root.mergeSortBottomUp = factory();
   }
-}(this, function (assert) {
+}(this, function () {
   'use strict';
 
-  var mergeSortBottomUp = {
-    sort: sort
-  };
+  var algorithm = {
 
-  function sort(array, compareFunc) {
-    var workArray = new Array(array.length);
-    var chunkSize = 1;
-    while (chunkSize < array.length) {
-      var i = 0;
-      while (i < array.length - chunkSize) {
-        bottomUpMerge(array, i, chunkSize, workArray, compareFunc);
-        i += chunkSize * 2;
+    sort: function (array) {
+      var workArray = new Array(array.length);
+      var chunkSize = 1;
+      while (chunkSize < array.length) {
+        var i = 0;
+        while (i < array.length - chunkSize) {
+          bottomUpMerge(array, i, chunkSize, workArray);
+          i += chunkSize * 2;
+        }
+        chunkSize *= 2;
       }
-      chunkSize *= 2;
+      return array;
+    },
+
+    // Compares elements at indexes `a` and `b`. Returns 0 if they're equal, a
+    // positive number if `a` is larger or a negative number if `b` is larger.
+    compare: function (a, b) {
+      if (a > b) {
+        return 1;
+      }
+      if (a < b) {
+        return -1;
+      }
+      return 0;
     }
-    return array;
-  }
 
-  function bottomUpMerge(array, leftPosition, chunkSize, workArray, compareFunc) {
+  };
+
+  function bottomUpMerge(
+      array, leftPosition, chunkSize, workArray) {
     var i;
     var rightPosition = leftPosition + chunkSize;
-    var endPosition = Math.min(leftPosition + chunkSize * 2 - 1, array.length - 1);
+    var endPosition = Math.min(leftPosition + chunkSize * 2 - 1,
+                               array.length - 1);
     var leftIndex = leftPosition;
@@ -52,3 +57,3 @@ var rightIndex = rightPosition;
           (rightIndex > endPosition ||
-          compare(array[leftIndex], array[rightIndex], compareFunc) <= 0)) {
+          algorithm.compare(array[leftIndex], array[rightIndex]) <= 0)) {
         workArray[i] = array[leftIndex++];
@@ -65,10 +70,3 @@ } else {
 
-  function compare(a, b, compareFunc) {
-    if (compareFunc) {
-      return compareFunc(a, b);
-    }
-    return a - b;
-  }
-
-  return mergeSortBottomUp;
+  return algorithm;
 }));

src/merge-sort.js

@@ -1,10 +0,1 @@
-// Explanation: http://www.growingwiththeweb.com/2012/11/algorithm-merge-sort.html
-//
-// Complexity (n=input size)
-//   Time, worse case:   O(n log n)
-//   Time, best case:    O(n log n)
-//   Time, average case: O(n log n)
-//   Space worst case:   O(n) auxiliary
-
-// UMD pattern: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
 (function (root, factory) {
@@ -21,29 +12,42 @@ 'use strict';
   }
-}(this, function (assert) {
+}(this, function () {
   'use strict';
 
-  var mergeSort = {
-    sort: sort
-  };
+  var algorithm = {
 
-  function sort(array, compareFunc) {
-    if (array.length <= 1)
-      return array;
-    
-    var i;
-    var middle = Math.floor(array.length / 2);
-    var left = new Array(middle);
-    var right = new Array(array.length - middle);
-    
-    for (i = 0; i < left.length; i++) {
-      left[i] = array[i];
+    sort: function (array) {
+      if (array.length <= 1) {
+        return array;
+      }
+
+      var i;
+      var middle = Math.floor(array.length / 2);
+      var left = new Array(middle);
+      var right = new Array(array.length - middle);
+
+      for (i = 0; i < left.length; i++) {
+        left[i] = array[i];
+      }
+      for (i = 0; i < right.length; i++) {
+        right[i] = array[i + left.length];
+      }
+
+      return merge(algorithm.sort(left), algorithm.sort(right));
+    },
+
+    // Compares elements at indexes `a` and `b`. Returns 0 if they're equal, a
+    // positive number if `a` is larger or a negative number if `b` is larger.
+    compare: function (a, b) {
+      if (a > b) {
+        return 1;
+      }
+      if (a < b) {
+        return -1;
+      }
+      return 0;
     }
-    for (i = 0; i < right.length; i++) {
-      right[i] = array[i + left.length];
-    }
-    
-    return merge(sort(left, compareFunc), sort(right, compareFunc), compareFunc);
+
   };
 
-  function merge(left, right, compareFunc) {
+  function merge(left, right) {
     var result = new Array(left.length + right.length);
@@ -53,6 +57,6 @@ var leftIndex = 0;
     var resultIndex = 0;
-    
+
     while (leftIndex < left.length || rightIndex < right.length) {
       if (leftIndex < left.length && rightIndex < right.length) {
-        if (compare(left[leftIndex], right[rightIndex], compareFunc) <= 0) {
+        if (algorithm.compare(left[leftIndex], right[rightIndex]) <= 0) {
           result[resultIndex++] = left[leftIndex++];
@@ -71,10 +75,3 @@ } else {
 
-  function compare(a, b, compareFunc) {
-    if (compareFunc) {
-      return compareFunc(a, b);
-    }
-    return a - b;
-  }
-
-  return mergeSort;
+  return algorithm;
 }));

src/quicksort.js

@@ -1,10 +0,1 @@
-// Explanation: http://www.growingwiththeweb.com/2012/12/algorithm-quicksort.html
-//
-// Complexity (n=input size)
-//   Time, worse case:   O(n^2)
-//   Time, best case:    O(n log n)
-//   Time, average case: O(n log n)
-//   Space worst case:   O(log n) auxiliary
-
-// UMD pattern: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
 (function (root, factory) {
@@ -21,29 +12,50 @@ 'use strict';
   }
-}(this, function (assert) {
+}(this, function () {
   'use strict';
 
-  var quicksort = {
-    sort: sort
+  var algorithm = {
+
+    sort: function (array) {
+      sortInternal(array, 0, array.length - 1);
+      return array;
+    },
+
+    // Swaps elements at indexes `a` and `b`.
+    swap: function (array, a, b) {
+      var temp = array[a];
+      array[a] = array[b];
+      array[b] = temp;
+    },
+
+    // Compares elements at indexes `a` and `b`. Returns 0 if they're equal, a
+    // positive number if `a` is larger or a negative number if `b` is larger.
+    compare: function (a, b) {
+      if (a > b) {
+        return 1;
+      }
+      if (a < b) {
+        return -1;
+      }
+      return 0;
+    }
+
   };
 
-  function sort(array, compareFunc) {
-    sortInternal(array, 0, array.length - 1, compareFunc);
-    return array;
-  }
-
-  function sortInternal(array, left, right, compareFunc) {
+  function sortInternal(array, left, right) {
     if (left < right) {
-      var pivot = partitionRandom(array, left, right, compareFunc);
-      sortInternal(array, left, pivot - 1, compareFunc);
-      sortInternal(array, pivot + 1, right, compareFunc);
+      var pivot = partitionRandom(array, left, right);
+      sortInternal(array, left, pivot - 1);
+      sortInternal(array, pivot + 1, right);
     }
   }
 
-  function partitionRandom(array, left, right, compareFunc) {
+  function partitionRandom(array, left, right) {
     var pivot = left + Math.floor(Math.random() * (right - left));
-    swap(array, right, pivot);
-    return partitionRight(array, left, right, compareFunc);
+    if (pivot !== right) {
+      algorithm.swap(array, right, pivot);
+    }
+    return partitionRight(array, left, right);
   }
 
-  function partitionRight(array, left, right, compareFunc) {
+  function partitionRight(array, left, right) {
     var pivot = array[right];
@@ -53,7 +65,12 @@ var mid = left;
     for (var i = mid; i < right; i++) {
-      if (compare(array[i], pivot, compareFunc) <= 0) {
-        swap(array, i, mid++);
+      if (algorithm.compare(array[i], pivot) <= 0) {
+        if (i !== mid) {
+          algorithm.swap(array, i, mid);
+        }
+        mid++;
       }
     }
-    swap(array, right, mid);
+    if (right !== mid) {
+      algorithm.swap(array, right, mid);
+    }
 
@@ -63,18 +80,3 @@ return mid;
 
-  function swap(array, a, b) {
-    if (a != b) {
-      var temp = array[a];
-      array[a] = array[b];
-      array[b] = temp;
-    }
-  }
-
-  function compare(a, b, compareFunc) {
-    if (compareFunc) {
-      return compareFunc(a, b);
-    }
-    return a - b;
-  }
-
-  return quicksort;
+  return algorithm;
 }));

src/selection-sort.js

@@ -1,10 +0,1 @@
-// Explanation: http://www.growingwiththeweb.com/2013/12/selection-sort.html
-//
-// Complexity (n=input size)
-//   Time, worse case:   O(n^2)
-//   Time, best case:    O(n^2)
-//   Time, average case: O(n^2)
-//   Space worst case:   O(1) auxiliary
-
-// UMD pattern: https://github.com/umdjs/umd/blob/master/returnExportsGlobal.js
 (function (root, factory) {
@@ -21,41 +12,47 @@ 'use strict';
   }
-}(this, function (assert) {
+}(this, function () {
   'use strict';
 
-  var selectionSort = {
-    sort: sort
-  };
+  var algorithm = {
 
-  function sort(array, compareFunc) {
-    for (var i = 0; i < array.length - 1; i++) {
-      var minIndex = i;
+    sort: function (array) {
+      for (var i = 0; i < array.length - 1; i++) {
+        var minIndex = i;
 
-      for (var j = i + 1; j < array.length; j++) {
-        if (compare(array[j], array[minIndex], compareFunc) < 0) {
-          minIndex = j;
+        for (var j = i + 1; j < array.length; j++) {
+          if (algorithm.compare(array[j], array[minIndex]) < 0) {
+            minIndex = j;
+          }
         }
-      }
 
-      if (minIndex != i) {
-        swap(array, i, minIndex);
+        if (minIndex !== i) {
+          algorithm.swap(array, i, minIndex);
+        }
       }
-    }
 
-    return array;
-  }
+      return array;
+    },
 
-  function swap(array, a, b) {
-    var temp = array[a];
-    array[a] = array[b];
-    array[b] = temp;
-  }
+    // Swaps elements at indexes `a` and `b`.
+    swap: function (array, a, b) {
+      var temp = array[a];
+      array[a] = array[b];
+      array[b] = temp;
+    },
 
-  function compare(a, b, compareFunc) {
-    if (compareFunc) {
-      return compareFunc(a, b);
+    // Compares elements at indexes `a` and `b`. Returns 0 if they're equal, a
+    // positive number if `a` is larger or a negative number if `b` is larger.
+    compare: function (a, b) {
+      if (a > b) {
+        return 1;
+      }
+      if (a < b) {
+        return -1;
+      }
+      return 0;
     }
-    return a - b;
-  }
 
-  return selectionSort;
+  };
+
+  return algorithm;
 }));

test/bubble-sort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/bubble-sort");
 
-testHelper.runTests("bubble-sort", algorithm.sort);
-testHelper.runCustomComparisonTests("bubble-sort custom comparison", algorithm.sort)
+describe("bubble-sort", function () {
+  testHelper.runIntegerTests(algorithm);
+  testHelper.runStringTests(algorithm);
+  testHelper.runCustomComparisonTests(algorithm);
+});

test/counting-sort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/counting-sort");
 
-// Test sort(array, maxValue) for arrays with non-negative values.
 describe("counting-sort", function () {
-  for (var i = 0; i < testHelper.tests.length; i++) {
-    (function (test) {
-      var sorted = testHelper.getSorted(test);
-      var original = testHelper.getOriginal(test);
-      var minValue = sorted[0];
-      var maxValue = sorted[sorted.length - 1];
+  // sort(array, maxValue) for arrays with non-negative values only.
+  describe("sort(array, maxValue)", function () {
+    for (var i = 0; i < testHelper.integerTests.length; i++) {
+      (function (test) {
+        var sorted = testHelper.getSorted(test);
+        var original = testHelper.getOriginal(test);
+        var minValue = sorted[0];
+        var maxValue = sorted[sorted.length - 1];
 
-      if (minValue >= 0) {
+        if (minValue >= 0) {
+          it(test.it, function () {
+            expect(algorithm.sort(original, maxValue))
+              .toEqual(sorted);
+          });
+        }
+      })(testHelper.integerTests[i]);
+    }
+  });
+
+  // Test sort(array, minValue, maxValue) for arrays with a specific range.
+  describe("sort(array, minValue, maxValue)", function () {
+    for (var i = 0; i < testHelper.integerTests.length; i++) {
+      (function (test) {
+        var sorted = testHelper.getSorted(test);
+        var original = testHelper.getOriginal(test);
+        var minValue = sorted[0];
+        var maxValue = sorted[sorted.length - 1];
+
         it(test.it, function () {
-          expect(algorithm.sort(original, maxValue))
+          expect(algorithm.sort(original, minValue, maxValue))
             .toEqual(sorted);
         });
-      }
-    })(testHelper.tests[i]);
-  }
-});
+      })(testHelper.integerTests[i]);
+    }
+  });
 
-// Test sort(array, minValue, maxValue) for arrays with a specific range.
-describe("counting-sort", function () {
-  for (var i = 0; i < testHelper.tests.length; i++) {
-    (function (test) {
-      var sorted = testHelper.getSorted(test);
-      var original = testHelper.getOriginal(test);
-      var minValue = sorted[0];
-      var maxValue = sorted[sorted.length - 1];
+  describe("sort(...)", function () {
+    it("should throw an exception with 1 argument", function () {
+      expect(function () {
+        algorithm.sort(1);
+      }).toThrow("Cannot sort with counting sort with 1 arguments");
+    });
 
-      it(test.it, function () {
-        expect(algorithm.sort(original, minValue, maxValue))
-          .toEqual(sorted);
-      });
-    })(testHelper.tests[i]);
-  }
+    it("should throw an exception with > 3 arguments", function () {
+      expect(function () {
+        algorithm.sort(1, 2, 3, 4);
+      }).toThrow("Cannot sort with counting sort with 4 arguments");
+    });
+  });
 });

test/heapsort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/heapsort");
 
-testHelper.runTests("heapsort", algorithm.sort);
-testHelper.runCustomComparisonTests("heapsort custom comparison", algorithm.sort);
+describe("heapsort", function () {
+  testHelper.runIntegerTests(algorithm);
+  testHelper.runStringTests(algorithm);
+  testHelper.runCustomComparisonTests(algorithm);
+});

test/insertion-sort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/insertion-sort");
 
-testHelper.runTests("insertion-sort", algorithm.sort);
-testHelper.runCustomComparisonTests("insertion-sort custom comparison", algorithm.sort);
+describe("insertion-sort", function () {
+  testHelper.runIntegerTests(algorithm);
+  testHelper.runStringTests(algorithm);
+  testHelper.runCustomComparisonTests(algorithm);
+});

test/merge-sort-bottom-up-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/merge-sort-bottom-up");
 
-testHelper.runTests("merge-sort-bottom-up", algorithm.sort);
-testHelper.runCustomComparisonTests("merge-sort-bottom-up custom comparison", algorithm.sort);
+describe("merge-sort-bottom-up", function () {
+  testHelper.runIntegerTests(algorithm);
+  testHelper.runStringTests(algorithm);
+  testHelper.runCustomComparisonTests(algorithm);
+});

test/merge-sort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/merge-sort");
 
-testHelper.runTests("merge-sort", algorithm.sort);
-testHelper.runCustomComparisonTests("merge-sort custom comparison", algorithm.sort);
+describe("merge-sort", function () {
+  testHelper.runIntegerTests(algorithm);
+  testHelper.runStringTests(algorithm);
+  testHelper.runCustomComparisonTests(algorithm);
+});

test/quicksort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/quicksort");
 
-testHelper.runTests("quicksort", algorithm.sort);
-testHelper.runCustomComparisonTests("quicksort custom comparison", algorithm.sort);
+describe("quicksort", function () {
+  testHelper.runIntegerTests(algorithm);
+  testHelper.runStringTests(algorithm);
+  testHelper.runCustomComparisonTests(algorithm);
+});

test/selection-sort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/selection-sort");
 
-testHelper.runTests("selection-sort", algorithm.sort);
-testHelper.runCustomComparisonTests("selection-sort custom comparison", algorithm.sort);
+describe("selection-sort", function () {
+  testHelper.runIntegerTests(algorithm);
+  testHelper.runStringTests(algorithm);
+  testHelper.runCustomComparisonTests(algorithm);
+});

test/test-helper.js

 var testHelper = {};
 
-testHelper.tests = require("./data/regular-tests");
-testHelper.reverseTests = require("./data/reverse-tests");
+testHelper.integerTests = require("./data/integer-tests");
+testHelper.integerReverseTests = require("./data/integer-reverse-tests");
+testHelper.stringTests = require("./data/string-tests");
 
-// This function expects algorithm to be a function that takes an array as an
-// argument and returnsa sorted array. The array returned may or may not be the
-// array passed in as an argument.
-testHelper.runTests = function (name, algorithm) {
-  describe(name, function () {
-    for (var i = 0; i < testHelper.tests.length; i++) {
+// Test sorting integer arrays.
+testHelper.runIntegerTests = function (algorithm) {
+  describe('integer tests', function () {
+    for (var i = 0; i < testHelper.integerTests.length; i++) {
       (function (test) {
         it(test.it, function () {
-          expect(algorithm(testHelper.getOriginal(test)))
+          expect(algorithm.sort(testHelper.getOriginal(test)))
             .toEqual(testHelper.getSorted(test));
         });
-      })(testHelper.tests[i]);
+      })(testHelper.integerTests[i]);
     }
@@ -22,27 +21,41 @@ });
 
-// Like runTests but runs the algorithm passing in a custom comparison function
-// to sort both normally and in reverse.
-testHelper.runCustomComparisonTests = function (name, algorithm) {
-  describe(name, function () {
-    for (var i = 0; i < testHelper.reverseTests.length; i++) {
+// Test sorting character and string arrays. These will only work on comparison
+// sorts.
+testHelper.runStringTests = function (algorithm) {
+  describe('string tests', function () {
+    for (var i = 0; i < testHelper.stringTests.length; i++) {
       (function (test) {
         it(test.it, function () {
-          var compare = function (a, b) {
+          expect(algorithm.sort(testHelper.getOriginal(test)))
+            .toEqual(testHelper.getSorted(test));
+        });
+      })(testHelper.stringTests[i]);
+    }
+  });
+};
+
+// Test sorting both normally and in reverse using custom comparison functions.
+testHelper.runCustomComparisonTests = function (algorithm) {
+  describe('custom comparison tests', function () {
+    for (var i = 0; i < testHelper.integerReverseTests.length; i++) {
+      (function (test) {
+        it(test.it, function () {
+          algorithm.compare = function (a, b) {
             return b - a;
           };
-          expect(algorithm(testHelper.getOriginal(test), compare))
+          expect(algorithm.sort(testHelper.getOriginal(test)))
             .toEqual(testHelper.getSorted(test));
         });
-      })(testHelper.reverseTests[i]);
+      })(testHelper.integerReverseTests[i]);
     }
-    for (var i = 0; i < testHelper.tests.length; i++) {
+    for (var i = 0; i < testHelper.integerTests.length; i++) {
       (function (test) {
         it(test.it, function () {
-          var compare = function (a, b) {
+          algorithm.compare = function (a, b) {
             return a - b;
           };
-          expect(algorithm(testHelper.getOriginal(test), compare))
+          expect(algorithm.sort(testHelper.getOriginal(test)))
             .toEqual(testHelper.getSorted(test));
         });
-      })(testHelper.tests[i]);
+      })(testHelper.integerTests[i]);
     }
@@ -49,0 +62,0 @@ });

New alerts

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

80755

increased by158.86%

Number of package files

63

increased by142.31%

Lines of code

1807

increased by140.61%

Number of lines in readme file

124

increased by396%

Worsened metrics

Dev dependency count

7

increased by600%

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes