Algoritmo de QuickSelection para encontrar a mediana e o i-ésimo elemento de um vetor

QuickSelection.py

import sys

Alunos = ["Maria Do Carmo", "Pedro Henrique", "Otacilio Maia"]

"""
Este algoritmo trata-se de uma otimização do Quicksort e é chamado de QuickSelect
Em vez de procurar ordernar todos os elementos inferiores do pivot
Este algoritmo apenas garante que existam k-1 elementos menores que o pivot
Mesmo que este subarray de k-1 menores que o pivot não estejam em ordem,
sendo este um critério de parada, no pior caso a complexidade é igual a do quicksort,
sendo O(n²), pois ele teria quer percorrer o array por completo. 
Porém diferente do quicksort que percorre os subarray da esquerda e direita
o Quickselect percorre apenas um lado do subarray, fazendo com que o caso médio seja
de menor complexidade que o do quicksort, operando em o(n) na média.
"""

def get_k_smallest(array, left_ordered_index, last_array_index, k):
    """
    Essa função vai procurar o 'k' menor elemento em um array qualquer.

    :param array: O array que vai conter os elementos originais.
    :param left_ordered_index: O ultimo index do ordenamento do array a esquerda.
    :param last_array_index: É o ultimo índice do array a ser visitado
    :param k: O elemento a ser procurado
    
    return: Ela retorna o 'k' menor elemento do array 
    """
    
    # Confere se o espaço de busca é válido
    if (k > 0 and k <= last_array_index - left_ordered_index + 1): 
      
	    # Considera o ultimo elemento como pivot, e particiona a lista com os menores que o pivot para a esquerda e maiores que o pivot para a direita
        position = partition(array, left_ordered_index, last_array_index)
  
        # Aqui tem um "pulo do gato" do algoritmo, que é o de ao garantir K-1 elementos menores que o pivot, 
        # o pivot é o k-esimo elemento sendo um critério de parada
        # Ou seja, a partir do momento que o código garante que os elementos que estão a esquerda são os elementos menores do que ele.
        if (position - left_ordered_index == k - 1):
            return array[position]
            

        # Se a posição do array for maior do que k-1 ele vai procurar no subarray da esquerda 
        if (position - left_ordered_index > k - 1): 
            return get_k_smallest(array, left_ordered_index, position - 1, k)
        
        # Se a posicao for menor que o k-1 o algoritmo precisa procurar no subarray da direita 
        return get_k_smallest(array, position + 1, last_array_index,
                            k - position + left_ordered_index - 1)
  
    # Se o k for mais do que a quantidade de elementos do array retornar um numero grande qualquer
    return sys.maxsize


# Na particao ele utiliza o elemento R, que é o ultimo elemento,
# como pivot e coloca todos os menores na esquerda
# e todos os maiores na direita
def partition(array, left_ordered_index, last_array_index):
    """ 
    Esta função retorna uma partição de cada array 

    :param array: O array que vai conter os elementos originais.
    :param left_ordered_index: O ultimo index do ordenamento do array a esquerda.
    :param last_array_index: É o ultimo índice do array a ser visitado
    
    return: Índice do array posicionado 
    """

    x = array[last_array_index]
    i = left_ordered_index
    
    for j in range(left_ordered_index, last_array_index):
        if (array[j] <= x):
            array[i], array[j] = array[j], array[i]
            i += 1
    array[i], array[last_array_index] = array[last_array_index], array[i]
    return i
  

def get_median(array):
    """ 
    Essa função retorna a media de um array, com base no algoritmo de quick selection. 
    Caso o array tiver um tamanho par a ele vai retornar a soma dos dois elementos centrais divididos por dois
    
    :param array: O array que vai conter os elementos originais.

    return: Esta função retorna o a mediana do array
    """
    
    # Se a o array for impar será seu elemento central de um array ordenado 
    # (neste caso o array por completo não esta ordenado porém o elemento central estão em sua posição corretas)
    if len(median_array) % 2:
        half_index = (len(median_array) + 1) / 2
        median = get_k_smallest(median_array, 0, len(median_array) - 1, half_index)

        return median        
        
    # Se o array for par será a soma de seus dois elementos centrais divididos por dois 
    # (neste caso o array por completo não esta ordenado porém os elementos centrais estão em suas posições corretas)
    else:
        half_left_index = (len(median_array)) / 2
        half_right_index = half_left_index+1
        
        median_left = get_k_smallest(median_array, 0, len(median_array) - 1, half_left_index)
        median_right = get_k_smallest(median_array, 0, len(median_array) - 1, half_right_index)
        median = (median_left + median_right) / 2
        
        return  median


if __name__ == "__main__":
      
    kth_array = [12, 3, 5, 7, 4, 19, 26]
    median_array= [2, 3, 5, 1, 7, 26] 

    k = 3

    print("O k menor elemento do array é: ", 
           get_k_smallest(kth_array, 0, len(kth_array) - 1, k))
    print("A mediana do array é: ", get_median(median_array))