quick_select.py

import random
import colorama
from colorama import Fore

colorama.init(autoreset=True)

def quick_select(arr, k):
    """
    Finds the k-th smallest element in an unsorted array using the Quick Select algorithm.

    :param arr: List of numbers
    :param k: Position (1-indexed) of the element to find
    :return: k-th smallest element
    :raises ValueError: If k is out of bounds
    """
    # Input validation
    if not isinstance(arr, list) or len(arr) == 0:
        raise ValueError("Input must be a non-empty list.")
    
    if not (1 <= k <= len(arr)):
        raise ValueError("k must be between 1 and the length of the array.")

    if len(arr) == 1:
        return arr[0]

    # Choose a random pivot
    pivot = random.choice(arr)
    
    # Partitioning the array into three parts
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    # Recursive selection based on the size of left partition
    if k <= len(left):
        return quick_select(left, k)
    elif k <= len(left) + len(mid):
        return pivot
    else:
        return quick_select(right, k - len(left) - len(mid))

if __name__ == "__main__":
    # Example usage
    numbers = [12, 4, 19, 33, 7, 1, 25, 18]
    k = 3  # Looking for the 3rd smallest element

    print(Fore.GREEN + "Array of numbers:", numbers)
    kth_element = quick_select(numbers, k)
    print(Fore.YELLOW + f"{k}-rd smallest element: {kth_element}")