Back to Repositories

Testing Insertion Sort Algorithm Implementation in javascript-algorithms

This test suite thoroughly validates the Insertion Sort algorithm implementation, focusing on sorting functionality, performance characteristics, and edge cases. The tests verify both basic sorting capabilities and advanced features like custom comparators and stability requirements.

Test Coverage Overview

The test suite provides comprehensive coverage of the Insertion Sort algorithm.

Basic array sorting validation
Custom comparator functionality testing
Stability verification for sorting operations
Negative number handling
Time complexity validation across different array types

Implementation Analysis

The testing approach utilizes Jest’s describe/it pattern for structured test organization. Each test case focuses on specific aspects of the sorting algorithm, with particular attention to performance metrics through visit count validation.

The implementation leverages the SortTester utility class for consistent testing patterns across different array types and conditions.

Technical Details

Testing Infrastructure:

Jest testing framework
SortTester utility class for standardized testing
Complexity constants for performance validation
Custom array types: sorted, unsorted, reverse sorted, and equal elements

Best Practices Demonstrated

The test suite exemplifies high-quality testing practices with clear separation of concerns and comprehensive coverage.

Consistent test case organization
Performance benchmarking with visit counts
Edge case handling
Reusable test utilities
Clear test descriptions

trekhleb/javascript-algorithms

src/algorithms/sorting/insertion-sort/__test__/InsertionSort.test.js

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

// Complexity constants.
const SORTED_ARRAY_VISITING_COUNT = 19;
const NOT_SORTED_ARRAY_VISITING_COUNT = 100;
const REVERSE_SORTED_ARRAY_VISITING_COUNT = 209;
const EQUAL_ARRAY_VISITING_COUNT = 19;

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

  it('should sort array with custom comparator', () => {
    SortTester.testSortWithCustomComparator(InsertionSort);
  });

  it('should do stable sorting', () => {
    SortTester.testSortStability(InsertionSort);
  });

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

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

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

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

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