Back to Repositories

Testing Counting Sort Algorithm Implementation in javascript-algorithms

This test suite validates the implementation of Counting Sort algorithm, focusing on sorting functionality, performance metrics, and edge cases. The tests verify both basic sorting capabilities and specific optimizations for known integer ranges.

Test Coverage Overview

The test suite provides comprehensive coverage of the Counting Sort implementation.

Key areas tested include:

Basic array sorting functionality
Handling of negative numbers
Optimized sorting with known min/max values
Performance validation across different array types

Implementation Analysis

The testing approach utilizes Jest’s testing framework with a custom SortTester utility for standardized sort validation.

Key patterns include:

Callback function mocking for operation counting
Time complexity verification through visit counting
Parameterized testing for different array types

Technical Details

Testing infrastructure includes:

Jest testing framework
Custom SortTester utility class
Mock functions for performance tracking
Predefined test arrays (sorted, unsorted, reverse, equal)
Complexity constants for visit count validation

Best Practices Demonstrated

The test suite exemplifies strong testing practices through isolation of test cases and comprehensive coverage.

Notable practices include:

Separate test cases for distinct functionality
Performance optimization validation
Edge case handling verification
Consistent complexity validation across array types

trekhleb/javascript-algorithms

src/algorithms/sorting/counting-sort/__test__/CountingSort.test.js

            
import CountingSort from '../CountingSort';
import {
  equalArr,
  notSortedArr,
  reverseArr,
  sortedArr,
  SortTester,
} from '../../SortTester';

// Complexity constants.
const SORTED_ARRAY_VISITING_COUNT = 60;
const NOT_SORTED_ARRAY_VISITING_COUNT = 60;
const REVERSE_SORTED_ARRAY_VISITING_COUNT = 60;
const EQUAL_ARRAY_VISITING_COUNT = 60;

describe('CountingSort', () => {
  it('should sort array', () => {
    SortTester.testSort(CountingSort);
  });

  it('should sort negative numbers', () => {
    SortTester.testNegativeNumbersSort(CountingSort);
  });

  it('should allow to use specify max/min integer value in array to make sorting faster', () => {
    const visitingCallback = jest.fn();
    const sorter = new CountingSort({ visitingCallback });

    // Detect biggest number in array in prior.
    const biggestElement = Math.max(...notSortedArr);

    // Detect smallest number in array in prior.
    const smallestElement = Math.min(...notSortedArr);

    const sortedArray = sorter.sort(notSortedArr, smallestElement, biggestElement);

    expect(sortedArray).toEqual(sortedArr);
    // Normally visitingCallback is being called 60 times but in this case
    // it should be called only 40 times.
    expect(visitingCallback).toHaveBeenCalledTimes(40);
  });

  it('should visit EQUAL array element specified number of times', () => {
    SortTester.testAlgorithmTimeComplexity(
      CountingSort,
      equalArr,
      EQUAL_ARRAY_VISITING_COUNT,
    );
  });

  it('should visit SORTED array element specified number of times', () => {
    SortTester.testAlgorithmTimeComplexity(
      CountingSort,
      sortedArr,
      SORTED_ARRAY_VISITING_COUNT,
    );
  });

  it('should visit NOT SORTED array element specified number of times', () => {
    SortTester.testAlgorithmTimeComplexity(
      CountingSort,
      notSortedArr,
      NOT_SORTED_ARRAY_VISITING_COUNT,
    );
  });

  it('should visit REVERSE SORTED array element specified number of times', () => {
    SortTester.testAlgorithmTimeComplexity(
      CountingSort,
      reverseArr,
      REVERSE_SORTED_ARRAY_VISITING_COUNT,
    );
  });
});