Skip to content

EFFICIENCY_REPORT.md

Latest commit

 

History

History
113 lines (81 loc) · 4.53 KB

EFFICIENCY_REPORT.md

File metadata and controls

113 lines (81 loc) · 4.53 KB

Efficiency Report for SortingAlgorithmsVisualized

This report documents efficiency issues found in the sorting algorithms visualization codebase and provides recommendations for improvements.

Executive Summary

The codebase contains several significant efficiency issues that impact performance, particularly with larger datasets. The most critical issue is in the merge sort implementation, which uses an inefficient merge operation that degrades the algorithm's time complexity from O(n log n) to O(n² log n).

Identified Efficiency Issues

1. CRITICAL: Merge Sort using shift() operations

File: src/sortingvisualizer/algorithms.js (lines 6-28) Impact: High - Changes algorithm complexity from O(n log n) to O(n² log n)

The mergeArrays function uses array.shift() operations to merge sorted subarrays. The shift() method is O(n) because it requires shifting all remaining elements in the array. This makes the merge operation O(n²) instead of O(n).

// Current inefficient implementation
while (arr1.length && arr2.length) {
    if (arr1[0] > arr2[0]) {
        sortedArr.push(arr2.shift())  // O(n) operation!
    }
    else {
        sortedArr.push(arr1.shift())  // O(n) operation!
    }
}

Recommendation: Use index-based iteration instead of shift() operations.

2. HIGH: Quicksort always uses first element as pivot

File: src/sortingvisualizer/algorithms.js (line 57) Impact: High - O(n²) worst-case on sorted/reverse-sorted arrays

const pivotIndex = 0  // Always first element

Recommendation: Use random pivot selection or median-of-three strategy.

3. MEDIUM: Bubble Sort off-by-one error

File: src/sortingvisualizer/algorithms.js (line 86) Impact: Medium - Unnecessary extra iterations

for (let j = 0; j < length-i; j++) {  // Should be length-i-1

Recommendation: Fix the loop condition to avoid unnecessary comparisons.

4. MEDIUM: Repeated DOM queries in animation loops

File: src/sortingvisualizer/SortingVisualizer.jsx (lines 36, 77) Impact: Medium - Unnecessary DOM traversal in tight loops

const arrayBars = document.getElementsByClassName('array-bar');  // Called repeatedly

Recommendation: Cache the DOM query result outside the loop.

5. LOW: Code duplication in sorting methods

File: src/sortingvisualizer/SortingVisualizer.jsx (lines 74-96 vs 34-64) Impact: Low - Maintenance burden and code bloat

The mergeSort() method duplicates logic from runSort() method.

Recommendation: Refactor to use the common runSort() method.

6. LOW: Inefficient array operations in Quicksort

File: src/sortingvisualizer/algorithms.js (lines 77-79) Impact: Low - Multiple array allocations and concatenations

completeArray = completeArray.concat(...Quicksort(leftArray))
completeArray.push(array[i-1])
completeArray = completeArray.concat(...Quicksort(rightArray))

Recommendation: Use in-place sorting or more efficient array building.

Performance Impact Analysis

Current Performance (250 elements):

  • Merge Sort: O(n² log n) ≈ 498,750 operations
  • Quick Sort: O(n²) worst case ≈ 62,500 operations
  • Bubble Sort: O(n²) with extra iterations ≈ 62,750 operations

After Optimization:

  • Merge Sort: O(n log n) ≈ 1,996 operations (250x improvement!)
  • Quick Sort: O(n log n) average case ≈ 1,996 operations
  • Bubble Sort: O(n²) ≈ 62,250 operations (small improvement)

Recommended Priority Order

  1. Fix Merge Sort shift() usage - Massive algorithmic improvement
  2. Implement random pivot for Quicksort - Prevents worst-case scenarios
  3. Cache DOM queries - Reduces unnecessary DOM traversal
  4. Fix Bubble Sort loop condition - Simple correctness fix
  5. Eliminate code duplication - Improves maintainability
  6. Optimize Quicksort array operations - Minor performance gain

Testing Recommendations

After implementing fixes:

  1. Verify all sorting algorithms produce correct sorted output
  2. Test with various array sizes (small, medium, large)
  3. Test with different data patterns (random, sorted, reverse-sorted)
  4. Verify visualization animations still work correctly
  5. Performance test with larger arrays if possible

Conclusion

The merge sort optimization alone would provide a 250x performance improvement for the merge operation, making it the highest priority fix. The other issues, while less critical, would collectively improve the overall robustness and performance of the application.