algoritmo baseado em partição/pivoting para encontrar o nth-menor item em uma lista

quicksortNth.py

# helper para trocar a posição de dois itens em um array
def switch(items, posX, posY):
    temp = items[posX]
    items[posX] = items[posY]
    items[posY] = temp
    return items

# operação de partição. retorna a lista particionada
# o último parâmetro (opcional) diz qual será o pivô, se
#  não especificado, será right/2.
def partition(items, left, right, posPivot=None):
    if posPivot is None:
        posPivot = (left + right / 2)
    pivot = items[posPivot]

    done = False
    oldItems = items

    while not done:
        while items[left] < pivot:
            left += 1
        while items[right] > pivot:
            right -= 1
        if right <= left:
            done = True
        else:
            switch(items, left, right)
    return items

# revisando partição:
# * seleciona um elemento como pivô
# * move todos os elementos maiores que o pivô para depois dele
# * move todos os elementos menores que o pivô para antes dele

# note como o resultado de uma partição implica que, uma vez 
# selecionado o pivô, é garantido que este será colocado na posição que
# ele deveria ficar caso a lista estivesse ordenada, mesmo a lista não estando
# completamente ordenada.

# quicksort meramente realiza esta operação sucessivamente, em cada uma das duas
# metades particionadas (esquerda/direita do pivô) até que a lista inteira
# esteja ordenada.

# == Problema do nth-menor
# se você ordenar uma lista em ordem crescente, o nth-menor número será o número
# na Na posição. Eg, o menor número será o da primeira posição, o terceiro menor número o da terceira posição, etc.

# Digamos que você quer encontrar o menor item da lista - ou seja, caso a lista ficasse ordenada, o item na primeira posição.
# Agora, sabendo que APOS UMA PARTICAO, O PIVO SELECIONADO SEMPRE VAI ACABAR NA POSICAO CORRETA COMO SE O ARRAY TIVESSE ORDENADO, digamos que você sucessivamente aplica partição em uma lista, até escolher um pivô que acaba na PRIMEIRA posição. regardless do quão ordenada o restante da lista esteja e de quantas partições já fez ou ainda faltam para ordenar ela completamente, você sabe que assim que um pivô for colocado na primeira posição, este é o menor número da lista. não é necessário continuar particionando nada.

# ou seja, para encontrar o nth-menor elemento de uma lista usando um algoritmo baseado em quicksort:

# faça o quicksort, mas toda vez que você realizar uma partição, cheque:
# - qual foi o pivô selecionado, e para qual posição este pivô foi parar após a partição:
# -- se a nova posição do pivô == nth, retorne o pivô; você já encontrou o nth-menor.
# -- do contrário, continue particionadno como de costume no quicksort


# o algoritmo abaixo tenta fazer isso de forma otimizada mas NÃO está funcionando.
# sugiro que altere o seu algoritmo de quicksort existente para incluir a condicional/retorno acima.

def findNthSmallest(items, n=1):
    left, right = [0, len(items)-1]
    while True:
        posPivot = left + (right/2)
        pivot = items[posPivot]
        items = partition(items, left, right, posPivot)
        newPivotPos = items.index(pivot)
        if newPivotPos == n -1 :
            return pivot
        elif newPivotPos >= n:
            right = newPivotPos
        else: #this isn't working; with the given list sample, will fail w/ n>=5
            left = newPivotPos-1
    return None

items = [7, 3, 2, 5, 26, 10, 9, -5, 1]