Ruigu Electronic

import random

def quick_sort(arr):
    """
    Quick Sort (random pivot optimization): Sort the array in ascending order
    :param arr: The list to be sorted (supports numeric types)
    :return: The sorted list (creates new sub-arrays; does not modify the original array)
    """
    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr
    
    # Step 1: Choose a random pivot (avoids worst-case scenarios)
    pivot = random.choice(arr)
    
    # Step 2: Partition into three groups: elements < pivot, == pivot, > pivot
    left = [x for x in arr if x < pivot]    # Sub-array with elements smaller than pivot
    middle = [x for x in arr if x == pivot] # Sub-array with elements equal to pivot
    right = [x for x in arr if x > pivot]   # Sub-array with elements larger than pivot
    
    # Step 3: Recursively sort left and right sub-arrays, then combine results
    return quick_sort(left) + middle + quick_sort(right)

# In-place version (modifies original array, saves memory)
def quick_sort_in_place(arr, low=None, high=None):
    """
    In-place Quick Sort (more memory-efficient): Sort the array in ascending order
    :param arr: The list to be sorted
    :param low: Start index of the sub-array (default: 0)
    :param high: End index of the sub-array (default: len(arr)-1)
    :return: None (modifies the original array)
    """
    # Initialize low and high for the first call (no need to pass them manually)
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
    
    # Base case: if low >= high, the sub-array is already sorted
    if low >= high:
        return
    
    # Step 1: Partition the array and get the pivot's final index
    pivot_index = partition(arr, low, high)
    
    # Step 2: Recursively sort left (low to pivot_index-1) and right (pivot_index+1 to high)
    quick_sort_in_place(arr, low, pivot_index - 1)
    quick_sort_in_place(arr, pivot_index + 1, high)

def partition(arr, low, high):
    """
    Helper function for in-place Quick Sort: Partitions the sub-array [low, high]
    :return: The final index of the pivot element
    """
    # Choose the LAST element as the pivot (simple implementation)
    pivot = arr[high]
    
    # i: pointer for the "smaller element region" (initially before the first element)
    i = low - 1
    
    # Iterate through elements from low to high-1
    for j in range(low, high):
        # If current element is <= pivot, expand the smaller region and swap
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # Place the pivot in its final sorted position (between smaller and larger elements)
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1  # Return the pivot's final index

# Test cases
if __name__ == "__main__":
    # Test 1: Ordinary unordered array (standard version)
    test1 = [64, 34, 25, 12, 22, 11, 90]
    print("Standard Quick Sort - Before:", test1)
    sorted_test1 = quick_sort(test1)
    print("Standard Quick Sort - After:", sorted_test1)  # Output: [11, 12, 22, 25, 34, 64, 90]

    # Test 2: In-place version (modifies original array)
    test2 = [5, 3, 8, 3, 2, 7, 1, 9]
    print("\nIn-place Quick Sort - Before:", test2)
    quick_sort_in_place(test2)
    print("In-place Quick Sort - After:", test2)  # Output: [1, 2, 3, 3, 5, 7, 8, 9]

    # Test 3: Edge cases (empty array, single element, sorted array)
    test3 = []
    test4 = [42]
    test5 = [1, 2, 3, 4, 5]
    print("\nEmpty array sorted:", quick_sort(test3))  # Output: []
    print("Single element sorted:", quick_sort(test4))  # Output: [42]
    print("Already sorted array:", quick_sort(test5))  # Output: [1, 2, 3, 4, 5]

    # Test 4: Array with duplicates
    test6 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
    print("Array with duplicates sorted:", quick_sort(test6))  # Output: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]