Quick Sort Algorithm

# Quick Sort is a divide-and-conquer algorithm that:
# 1. Chooses a pivot element
# 2. Partitions array around pivot (smaller left, larger right)
# 3. Recursively sorts both partitions
#
# Time Complexity: O(n log n) average, O(n^2) worst case
# Space Complexity: O(log n) - recursion stack
# Stable: No
# In-place: Yes

class Solution:
    def quickSort(self, nums: List[int]) -> List[int]:
        """Quick sort - modifies array in place"""
        self.quickSortHelper(nums, 0, len(nums) - 1)
        return nums

    def quickSortHelper(self, nums: List[int], left: int, right: int) -> None:
        if left < right:
            # Partition and get pivot index
            pivot_index = self.partition(nums, left, right)

            # Recursively sort left and right partitions
            self.quickSortHelper(nums, left, pivot_index - 1)
            self.quickSortHelper(nums, pivot_index + 1, right)

    def partition(self, nums: List[int], left: int, right: int) -> int:
        """Lomuto partition scheme"""
        # Choose rightmost element as pivot
        pivot = nums[right]
        i = left - 1  # Index of smaller element

        for j in range(left, right):
            # If current element <= pivot
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]

        # Place pivot in correct position
        nums[i + 1], nums[right] = nums[right], nums[i + 1]
        return i + 1

    # Hoare partition scheme (alternative, slightly more efficient)
    def partitionHoare(self, nums: List[int], left: int, right: int) -> int:
        """Hoare partition scheme"""
        pivot = nums[left]
        i = left - 1
        j = right + 1

        while True:
            # Find element on left that should be on right
            i += 1
            while nums[i] < pivot:
                i += 1

            # Find element on right that should be on left
            j -= 1
            while nums[j] > pivot:
                j -= 1

            if i >= j:
                return j

            # Swap elements
            nums[i], nums[j] = nums[j], nums[i]

    # Randomized Quick Sort (avoids worst case)
    def quickSortRandomized(self, nums: List[int]) -> List[int]:
        import random

        def randomizedPartition(left, right):
            # Randomly choose pivot
            random_index = random.randint(left, right)
            nums[random_index], nums[right] = nums[right], nums[random_index]
            return self.partition(nums, left, right)

        def helper(left, right):
            if left < right:
                pivot_index = randomizedPartition(left, right)
                helper(left, pivot_index - 1)
                helper(pivot_index + 1, right)

        helper(0, len(nums) - 1)
        return nums

# Quick Sort Properties:
# ✓ In-place (O(1) extra space, excluding recursion)
# ✓ Fast in practice (good cache locality)
# ✓ Average O(n log n)
# ✗ Unstable
# ✗ Worst case O(n^2) (already sorted, bad pivot choice)
# ✗ Not suitable when guaranteed O(n log n) needed
#
# Partition Patterns:
# 1. Lomuto: Simpler, pivot at end
# 2. Hoare: More efficient, fewer swaps
# 3. Three-way: Handles duplicates well (Dutch National Flag)
#
# When to use Quick Sort:
# 1. General-purpose in-place sorting
# 2. Average case performance matters more than worst case
# 3. Good cache performance is important