js-sorting - npm Package Compare versions

Comparing version 1.0.0 to 1.1.0

package.json

 {
   "name": "js-sorting",
-  "version": "1.0.0",
+  "version": "1.1.0",
   "description": "A collection of sorting algorithms written in JavaScript.",
@@ -5,0 +5,0 @@ "devDependencies": {

src/bubble-sort.js

 // 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
@@ -3,0 +10,0 @@ (function (root, factory) {

src/counting-sort.js

 // 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
@@ -21,13 +28,55 @@ (function (root, factory) {
 
-  function sort(array, maxValue) {
-    var buckets = new Array(maxValue);
+  // 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);
+    }
+    if (arguments.length === 3) {
+      return sortWithMinAndMax.apply(null, arguments);
+    }
+    throw "Cannot sort with counting sort with " + arguments.length +
+      " arguments";
+  }
+
+  function sortWithMax(array, maxValue) {
+    var buckets = new Array(maxValue + 1);
     var sortedIndex = 0;
     var i;
 
+    for (i = 0; i < array.length; i++) {
+      if (!buckets[array[i]]) {
+        buckets[array[i]] = 0;
+      }
+      buckets[array[i]]++;
+    }
+
     for (i = 0; i < buckets.length; i++) {
-      buckets[i] = 0;
+      while (buckets[i] > 0) {
+        array[sortedIndex++] = i;
+        buckets[i]--;
+      }
     }
 
+    return array;
+  }
+
+  function sortWithMinAndMax(array, minValue, maxValue) {
+    if (array.length === 0) {
+      return array;
+    }
+
+    var rangeSize = maxValue - minValue;
+    var buckets = new Array(rangeSize);
+    var sortedIndex = 0;
+    var i;
+
     for (i = 0; i < array.length; i++) {
-      buckets[array[i]]++;
+      // Change the value to a zero-based index
+      var bucketIndex = array[i] - minValue;
+      if (!buckets[bucketIndex]) {
+        buckets[bucketIndex] = 0;
+      }
+      buckets[bucketIndex]++;
     }
@@ -37,3 +86,4 @@
       while (buckets[i] > 0) {
-        array[sortedIndex++] = i;
+        // Change the index to the correct value
+        array[sortedIndex++] = i + minValue;
         buckets[i]--;
@@ -40,0 +90,0 @@ }

src/heapsort.js

 // 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
@@ -33,4 +40,3 @@ (function (root, factory) {
   function buildHeap(array, heapSize) {
-    var i;
-    for (i = Math.floor(array.length / 2); i >= 0; i--)
+    for (var i = Math.floor(array.length / 2); i >= 0; i--)
       heapify(array, heapSize, i);
@@ -37,0 +43,0 @@ }

src/insertion-sort.js

 // 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
@@ -3,0 +10,0 @@ (function (root, factory) {

src/merge-sort-bottom-up.js

 // 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
@@ -3,0 +10,0 @@ (function (root, factory) {

src/merge-sort.js

 // 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
@@ -3,0 +10,0 @@ (function (root, factory) {

src/quicksort.js

 // 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
@@ -3,0 +10,0 @@ (function (root, factory) {

src/selection-sort.js

 // 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
@@ -3,0 +10,0 @@ (function (root, factory) {

test/bubble-sort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/bubble-sort");
 
-testHelper.testSortingAlgorithm("bubble-sort", algorithm.sort);
+testHelper.runTests("bubble-sort", algorithm.sort);

test/counting-sort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/counting-sort");
 
-testHelper.testSortingAlgorithm("counting-sort", algorithm.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];
+
+      if (minValue >= 0) {
+        it(test.it, function () {
+          expect(algorithm.sort(original, maxValue))
+            .toEqual(sorted);
+        });
+      }
+    })(testHelper.tests[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];
+
+      it(test.it, function () {
+        expect(algorithm.sort(original, minValue, maxValue))
+          .toEqual(sorted);
+      });
+    })(testHelper.tests[i]);
+  }
+});

test/heapsort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/heapsort");
 
-testHelper.testSortingAlgorithm("heapsort", algorithm.sort);
+testHelper.runTests("heapsort", algorithm.sort);

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

 var testHelper = require("./test-helper");
 var algorithm = require("../src/merge-sort-bottom-up");
 
-testHelper.testSortingAlgorithm("merge-sort-bottom-up", algorithm.sort);
+testHelper.runTests("merge-sort-bottom-up", algorithm.sort);

test/merge-sort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/merge-sort");
 
-testHelper.testSortingAlgorithm("merge-sort", algorithm.sort);
+testHelper.runTests("merge-sort", algorithm.sort);

test/quicksort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/quicksort");
 
-testHelper.testSortingAlgorithm("quicksort", algorithm.sort);
+testHelper.runTests("quicksort", algorithm.sort);

test/selection-sort-spec.js

 var testHelper = require("./test-helper");
 var algorithm = require("../src/selection-sort");
 
-testHelper.testSortingAlgorithm("selection-sort", algorithm.sort);
+testHelper.runTests("selection-sort", algorithm.sort);

test/test-helper.js

@@ -6,9 +6,11 @@ var testHelper = {};
 // array passed in as an argument.
-testHelper.testSortingAlgorithm = function (name, algorithm) {
+testHelper.runTests = function (name, algorithm) {
   describe(name, function () {
-    for (var i = 0; i < tests.length; i++) {
-      var test = tests[i];
-      it(test.it, function () {
-        expect(algorithm(test.original)).toEqual(test.sorted);
-      })
+    for (var i = 0; i < testHelper.tests.length; i++) {
+      (function (test) {
+        it(test.it, function () {
+          expect(algorithm(testHelper.getOriginal(test)))
+            .toEqual(testHelper.getSorted(test));
+        });
+      })(testHelper.tests[i]);
     }
@@ -18,3 +20,11 @@ });
 
-var tests = [{
+// Only test on copies of the test arrays
+testHelper.getOriginal = function (test) {
+  return test.original.slice(0);
+};
+testHelper.getSorted = function (test) {
+  return test.sorted.slice(0);
+}
+
+testHelper.tests = [{
   it: "Should sort empty array",
@@ -21,0 +31,0 @@ original: [],

No alert changes

Improved metrics

Total package byte prevSize

25424

increased by21.49%

Number of package files

23

increased by4.55%

Lines of code

609

increased by33.55%

No dependency changes