Back to Repositories

Testing QuickSort In-Place Implementation in javascript-algorithms

This test suite validates the in-place QuickSort implementation, focusing on array sorting functionality and algorithmic complexity. It verifies sorting behavior across different array types and ensures the algorithm maintains expected performance characteristics.

Test Coverage Overview

The test suite provides comprehensive coverage of QuickSort’s in-place implementation.

Key areas tested include:

Basic array sorting functionality
Custom comparator support
Negative number handling
Time complexity verification across different array types

Edge cases covered include sorted, reverse-sorted, and arrays with equal elements.

Implementation Analysis

The testing approach utilizes Jest’s describe/it pattern for structured test organization. Each test case leverages a shared SortTester utility, demonstrating modular test design.

The implementation specifically tracks element visit counts to verify algorithmic complexity, using constants like SORTED_ARRAY_VISITING_COUNT to validate performance characteristics.

Technical Details

Testing infrastructure includes:

Jest test framework
Custom SortTester utility class
Predefined test arrays (equalArr, notSortedArr, reverseArr, sortedArr)
Complexity validation through visit count tracking

Best Practices Demonstrated

The test suite exemplifies several testing best practices.

Notable approaches include:

Modular test organization
Reusable test utilities
Consistent complexity validation
Comprehensive edge case coverage
Clear test case naming conventions

trekhleb/javascript-algorithms

src/algorithms/sorting/quick-sort/__test__/QuickSortInPlace.test.js

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

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

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

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

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

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

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

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

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