feat: implement quicksort algorithm
Summary
This MR adds a complete implementation of the quicksort algorithm with two different approaches:
Implementations
-
quicksort() - Recursive implementation using list comprehensions
- Returns a new sorted list
- Simple and easy to understand
- Uses pivot selection from middle element
-
quicksort_inplace() - In-place implementation using Lomuto partition scheme
- Sorts the list in-place
- More memory efficient (O(log n) space)
- Uses last element as pivot
Features
-
✅ Both implementations handle all edge cases (empty list, single element, etc.) -
✅ Comprehensive test suite with 13 test cases -
✅ All tests pass successfully -
✅ Both implementations produce identical results -
✅ Well-documented code with docstrings
Test Coverage
- Empty list
- Single element list
- Already sorted list
- Reverse sorted list
- Random list
- List with duplicate elements
- Consistency between both implementations
Performance
- Time complexity: O(n log n) average, O(n²) worst-case
- Space complexity: O(n) for quicksort(), O(log n) for quicksort_inplace()
This implementation is ready for production use and follows best practices for algorithm implementation.