Olá a todos!
Estou com uma dúvida no algoritmo BFPRT mostrado na sala de aula.
Não implementei, mas estava fazendo a simulação dele na mão mesmo, e me parece que ele entra em um recursão infinita. Desculpem se comi alguma bola na simulação ou na explicação em sala de aula, mas creio que falta algo ai...
Por exemplo, quando n = 12, vamos ter 3 grupos de 5 (sendo um com apenas 2 elementos). A primeira partição coloca a mediana desses 3 grupos nas posições A[1..3]. Em seguida, o SELECT-BFPRT é chamado com parâmetros (A,1,3,2), ou seja, ele quer encontrar a mediana desse sub-vetor.
Na recurssão do SELECT-BFPRT, o primeiro passo é novamente fazer a partição de A[1..3], que ordena esse sub-vetor, pula as linhas 4-6 e chama novamente o SELECT-BPFRT, agora com parâmetros (A,1,1,1).
Ai está o problema (ao meu ver), não faz sentido mais particionar esse sub-vetor, porque só tem um elemento (e a mediana é esse elemento). Não deveria ter uma condição em SELECT-BFPRT antes da Partição???
Abraços,
Leandro