Back to Repositories

Testing HeapSort Algorithm Implementation in javascript-algorithms

This test suite validates the HeapSort algorithm implementation, focusing on sorting functionality and time complexity verification. The tests ensure the algorithm correctly handles various array types and maintains expected performance characteristics.

Test Coverage Overview

The test suite provides comprehensive coverage of HeapSort functionality:

Basic array sorting validation
Custom comparator functionality testing
Negative numbers handling
Time complexity verification across different array types (equal, sorted, unsorted, reverse)

Implementation Analysis

The testing approach utilizes Jest’s describe/it pattern for structured test organization. The implementation leverages a SortTester utility class for consistent validation across different array scenarios, with specific visiting count assertions to verify algorithmic complexity.

Technical Details

Testing Framework: Jest
Utility Classes: SortTester for standardized sort testing
Complexity Constants: Defined visit counts for different array types
Test Data: Pre-defined array variants (sorted, unsorted, reverse, equal)

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Modular test organization using describe blocks
Consistent complexity validation
Reusable test utilities
Comprehensive edge case coverage
Clear test case descriptions

trekhleb/javascript-algorithms

src/algorithms/sorting/heap-sort/__test__/HeapSort.test.js

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

// Complexity constants.
// These numbers don't take into account up/dow heapifying of the heap.
// Thus these numbers are higher in reality.
const SORTED_ARRAY_VISITING_COUNT = 40;
const NOT_SORTED_ARRAY_VISITING_COUNT = 40;
const REVERSE_SORTED_ARRAY_VISITING_COUNT = 40;
const EQUAL_ARRAY_VISITING_COUNT = 40;

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

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

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

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

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

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

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