quick_select_demo

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Filename: quick_select_demo.py
# Version: 1.0.0
# Author: Jeoi Reqi

"""
Description:
    This script demonstrates the Quick Select algorithm to find the k-th smallest element in an array.

Requirements:
    - Python 3.x

Functions:
    - quick_select(arr, k):
        Returns the k-th smallest element from the list `arr`.

Usage:
    - Run the script to see the Quick Select algorithm in action.

Example:

                :: QUICK SELECT DEMO ::

        Array: [3, 2, 1, 5, 4]
        k = 2 (looking for the 3rd smallest element)
        Result: 3

        Quick Select Complete!

            Exiting Program...   GoodBye!

Additional Notes:
    - Quick Select is efficient for finding the k-th smallest element in an unsorted array, with an average time complexity of O(n).
"""

import random

def quick_select(arr, k):
    """
    Returns the k-th smallest element of list `arr`.

    Args:
        arr (list): List of elements from which to find the k-th smallest element.
        k (int): Index of the smallest element to find (0-based).

    Returns:
        int: The k-th smallest element in the list `arr`.

    Example Output:

                :: QUICK SELECT DEMO ::

        Array: [3, 2, 1, 5, 4]
        k = 2 (looking for the 3rd smallest element)
        Result: 3

        Quick Select Complete!

                Exiting Program...   GoodBye!

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

    pivot = random.choice(arr)

    lows = [el for el in arr if el < pivot]
    highs = [el for el in arr if el > pivot]
    pivots = [el for el in arr if el == pivot]

    if k < len(lows):
        return quick_select(lows, k)
    elif k < len(lows) + len(pivots):
        return pivots[0]
    else:
        return quick_select(highs, k - len(lows) - len(pivots))

def main():
    """
    Main function to demonstrate quick select.

    It initializes an example array, uses quick_select function to find
    the k-th smallest element, and prints the original array and the result.
    """
    print("\n\t\t:: QUICK SELECT DEMO ::\n")

    # Example array
    arr = [3, 2, 1, 5, 4]
    k = 2  # looking for the 3rd smallest element, index 2

    # Print the original array
    arr_str = "["
    for index, num in enumerate(arr):
        if index == 0:
            arr_str += f"{num}"  # No leading space needed for the first number
        else:
            arr_str += f", {num}"  # Add a leading space for single-digit numbers
    arr_str += "]"
    print(f"Array: {arr_str}")

    # Perform quick select
    result = quick_select(arr, k)

    # Print the result
    print(f"k = {k} (looking for the {k+1}rd smallest element)")
    print(f"Result: {result}")

    # Print completion message
    print("\nQuick Select Complete!\n\n\tExiting Program...   GoodBye!")

if __name__ == "__main__":
    main()