Skip to content

Add Quick Sort Algorithm Implementation

Yun.Long requested to merge wip/quick-sort-implementation into main

Summary

Add two implementations of the Quick Sort algorithm to the sorting algorithms collection:

Features Added

  • quick_sort(): Classic recursive implementation using list comprehensions
  • quick_sort_inplace(): In-place implementation using partitioning

Algorithm Details

  • Time Complexity: O(n log n) average case, O(n²) worst case
  • Space Complexity: O(log n) for in-place, O(n) for classic version
  • Stability: Not stable (common for quick sort)

Testing

  • Both implementations pass all existing test cases
  • Added to the parameterized test suite
  • Verified non-mutating behavior

Implementation Notes

  • Follows the existing code style and patterns
  • Includes comprehensive docstrings
  • Uses type hints consistently
  • Maintains the same interface as other sorting functions

This adds a fundamental divide-and-conquer algorithm to the collection, complementing the existing bubble, insertion, selection, and merge sort implementations.

Merge request reports