Quick Sort

Quick sort is a divide-and-conquer algorithm that picks a 'pivot' element from the array and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Algorithm Overview

Quick sort works by selecting a 'pivot' element and partitioning the array around it. Elements smaller than the pivot go to the left, elements larger go to the right, and elements equal to the pivot can go either way. This process is repeated recursively on the sub-arrays.

Key Features

Divide and Conquer: Uses partitioning strategy
Not Stable: Does not preserve relative order of equal elements
In-Place: Can sort with minimal extra space
Cache Efficient: Good locality of reference
Average Case Optimal: Very fast in practice

Time and Space Complexity

Time Complexity:
Best Case: O(n log n) - balanced partitions
Average Case: O(n log n) - random pivots
Worst Case: O(n²) - already sorted with poor pivot choice
Space Complexity: O(log n) average due to recursion stack, O(n) worst case

Algorithm Steps

Choose a pivot element from the array
Partition the array around the pivot
Elements < pivot go to the left
Elements == pivot go to the middle
Elements > pivot go to the right
Recursively sort the left and right sub-arrays
Base case: Arrays with 0 or 1 element are already sorted

Usage Examples

Basic Usage

from algo.algorithms.sorting.quick_sort import quick_sort

# Sort integers (creates new array)
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = quick_sort(numbers)
print(sorted_numbers)  # [11, 12, 22, 25, 34, 64, 90]

# Sort strings
words = ['banana', 'apple', 'cherry']
sorted_words = quick_sort(words)
print(sorted_words)  # ['apple', 'banana', 'cherry']

# Empty array
result = quick_sort([])
print(result)  # []

In-Place Sorting

from algo.algorithms.sorting.quick_sort import quick_sort_in_place

# Modify original array
arr = [64, 34, 25, 12]
quick_sort_in_place(arr)
print(arr)  # [12, 25, 34, 64]

Randomized Quick Sort

from algo.algorithms.sorting.quick_sort import quick_sort_randomized

# Better average performance on sorted data
arr = [5, 4, 3, 2, 1]
quick_sort_randomized(arr)
print(arr)  # [1, 2, 3, 4, 5]

Educational/Debugging

from algo.algorithms.sorting.quick_sort import quick_sort_verbose

# See step-by-step process
quick_sort_verbose([64, 34, 25, 12])

Output:

Sorting: [64, 34, 25, 12]
  Chosen pivot: 25 (at index 2)
  Partitioning around pivot 25:
    64 > 25 -> right partition
    34 > 25 -> right partition
    25 == 25 -> middle partition
    12 < 25 -> left partition
  Left partition: [12]
  Middle partition (pivot values): [25]
  Right partition: [64, 34]
Recursively sorting left partition:
  Base case: [12] (already sorted)
Recursively sorting right partition:
  Sorting: [64, 34]
    Chosen pivot: 34 (at index 1)
    Partitioning around pivot 34:
      64 > 34 -> right partition
      34 == 34 -> middle partition
    Left partition: []
    Middle partition (pivot values): [34]
    Right partition: [64]
  Base case: [64] (already sorted)
  Combined result: [34, 64]
Combined result: [12, 25, 34, 64]

Edge Cases Handled

# Empty array
result = quick_sort([])  # Returns []

# Single element
result = quick_sort([42])  # Returns [42]

# Already sorted (use randomized version for better performance)
result = quick_sort_randomized([1, 2, 3, 4])  # O(n log n)

# Reverse sorted
result = quick_sort([4, 3, 2, 1])  # Returns [1, 2, 3, 4]

# Duplicates (3-way partitioning handles efficiently)
result = quick_sort([3, 1, 3, 1])  # Returns [1, 1, 3, 3]

API Reference

Quick Sort Algorithm Implementation

Quick sort is a divide-and-conquer algorithm that picks a 'pivot' element from the array and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Time Complexity: O(n log n) average case, O(n²) worst case, O(n log n) best case

Space Complexity: O(log n) average case due to recursion stack

Stability: Not stable (may change relative order of equal elements)

`quick_sort(arr)`

Sort an array using the quick sort algorithm.

The algorithm works by selecting a 'pivot' element and partitioning the array around the pivot, then recursively sorting the sub-arrays.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of comparable elements to sort	required

Returns:

Type	Description
`List[T]`	A new sorted list (does not modify the original array)

Examples:

>>> quick_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

>>> quick_sort(['banana', 'apple', 'cherry'])
['apple', 'banana', 'cherry']

>>> quick_sort([])
[]

`quick_sort_in_place(arr)`

Sort an array using quick sort algorithm with in-place modification.

This version modifies the original array instead of creating a new one. Uses the Lomuto partition scheme.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of comparable elements to sort	required

Returns:

Type	Description
`List[T]`	The sorted list (same object as input, modified in-place)

`quick_sort_randomized(arr)`

Quick sort with randomized pivot selection to avoid worst-case performance.

This version randomly selects the pivot to achieve better average performance and avoid the O(n²) worst-case on already sorted arrays.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of comparable elements to sort	required

Returns:

Type	Description
`List[T]`	The sorted list (same object as input, modified in-place)

`quick_sort_verbose(arr, depth=0)`

Quick sort with detailed step-by-step output for educational purposes.

This version prints each step of the divide-and-conquer process to help understand how the algorithm works.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of comparable elements to sort	required
`depth`	`int`	Current recursion depth (for indentation)	`0`

Returns:

Type	Description
`List[T]`	A new sorted list