Fix CountingSort for negative numbers (trekhleb#100)

dubzzz · trekhleb · commit 3be02b551993 · 2018-07-22T18:03:13.000+03:00
diff --git a/src/algorithms/sorting/counting-sort/CountingSort.js b/src/algorithms/sorting/counting-sort/CountingSort.js
@@ -5,8 +5,9 @@ export default class CountingSort extends Sort {
    * @param {number[]} originalArray
    * @param {number} [biggestElement]
    */
-  sort(originalArray, biggestElement = 0) {
+  sort(originalArray, smallestElement = 0, biggestElement = 0) {
     // Detect biggest element in array in order to build number bucket array later.
+    let detectedSmallestElement = smallestElement;
     let detectedBiggestElement = biggestElement;
     if (!detectedBiggestElement) {
       originalArray.forEach((element) => {
@@ -16,17 +17,20 @@ export default class CountingSort extends Sort {
         if (this.comparator.greaterThan(element, detectedBiggestElement)) {
           detectedBiggestElement = element;
         }
+        if (this.comparator.greaterThan(detectedSmallestElement, element)) {
+          detectedSmallestElement = element;
+        }
       });
     }
 
     // Init buckets array.
     // This array will hold frequency of each number from originalArray.
-    const buckets = Array(detectedBiggestElement + 1).fill(0);
+    const buckets = Array(detectedBiggestElement - detectedSmallestElement + 1).fill(0);
     originalArray.forEach((element) => {
       // Visit element.
       this.callbacks.visitingCallback(element);
 
-      buckets[element] += 1;
+      buckets[element - detectedSmallestElement] += 1;
     });
 
     // Add previous frequencies to the current one for each number in bucket
@@ -53,13 +57,13 @@ export default class CountingSort extends Sort {
       this.callbacks.visitingCallback(element);
 
       // Get correct position of this element in sorted array.
-      const elementSortedPosition = buckets[element];
+      const elementSortedPosition = buckets[element - detectedSmallestElement];
 
       // Put element into correct position in sorted array.
       sortedArray[elementSortedPosition] = element;
 
       // Increase position of current element in the bucket for future correct placements.
-      buckets[element] += 1;
+      buckets[element - detectedSmallestElement] += 1;
     }
 
     // Return sorted array.
diff --git a/src/algorithms/sorting/counting-sort/__test__/CountingSort.test.js b/src/algorithms/sorting/counting-sort/__test__/CountingSort.test.js
@@ -18,6 +18,10 @@ describe('CountingSort', () => {
     SortTester.testSort(CountingSort);
   });
 
+  it('should sort negative numbers', () => {
+    SortTester.testNegativeNumbersSort(CountingSort);
+  });
+
   it('should allow to use specify maximum integer value in array to make sorting faster', () => {
     const visitingCallback = jest.fn();
     const sorter = new CountingSort({ visitingCallback });
@@ -27,7 +31,7 @@ describe('CountingSort', () => {
       return element > accumulator ? element : accumulator;
     }, 0);
 
-    const sortedArray = sorter.sort(notSortedArr, biggestElement);
+    const sortedArray = sorter.sort(notSortedArr, 0, biggestElement);
 
     expect(sortedArray).toEqual(sortedArr);
     // Normally visitingCallback is being called 60 times but in this case
