K-Smallest element

📖

Este algorimo de búsqueda encontrará el

k

menor elemento de un array desordenado

ℹ️

Este algoritmo hace algo parecido al quicksort donde el grueso del algoritmo es el paso de dividir

Se recorre el array y se crean 3 sub-arrays con los número menores, iguales y mayores respecto de un número arbitrario

Si el número de elementos en el array low es menor que $k$ , entonces dicho número no puede estar en este array
Si el número de elementos es mayor que $k$ , entonces se hace la llamada recursiva

Descartamos los elementos del array low, por lo que restaremos a $k$ el número de elementos en dicho array

Si el número de elementos en el array equal es menor que $k$ , entonces dicho número no puede estar en este array
Si el número de elementos es mayor que $k$ , entonces se hace la llamada recursiva

Descartamos los elementos del array equal, por lo que restaremos a $k$ el número de elementos en dicho array

Por descarte el elemento estará en el array high así que hacemos la llamada recursiva con este array


# Finds the k-th smallest element in an array using the divide and conquer strategy.
def kSmallestElement(k, arr):
    # Prepare the pivot element.
    mid = len(arr) // 2
    pivot = arr[mid]
    
    ### Divide the array into three parts: low, equal and high.
    
    # low: elements less than the pivot.
    low = [x for x in arr if x < pivot]
    if k < len(low): # If k is less than the length of low, the k-th smallest element will be contained in low
        return kSmallestElement(k, low)
    
    # Since we know that the k-th smallest element is not in low, we can discard all elements in low, so we subtract the length of low from k (we are offseting the index of the k-th smallest element in the new array without the low elements)
    k -= len(low)
    # equal: elements equal to the pivot.
    equal = [x for x in arr if x == pivot]
    if k < len(equal):
        return pivot
    
    # Since we know that the k-th smallest element is not in equal, we can discard all elements in equal, so we subtract the length of equal from k (we are offseting the index of the k-th smallest element in the new array without the low and equal elements)
    k -= len(equal)
    # high: elements greater than the pivot.
    high = [x for x in arr if x > pivot]
    return kSmallestElement(k, high)

if __name__ == "__main__":
    arr = [12, 3, 5, 7, 4, 19, 26, 32, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31]
    
    print(kSmallestElement(0, arr))