MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-031

Enunciado: Considere o algoritmo SELECT a seguir, que retorna o i-ésimo menor elemento de um arranjo de entrada de tamanho n:

1: Dividir os n elementos do arranjo de entrada em grupos de 5 elementos cada e no máximo um grupo formado pelos n mod 5 elementos restantes.

2: Encontrar a mediana de cada um dos ceil(n/5) grupos, através da ordenação por inserção dos elementos de cada grupo (nos quais existem 5 elementos, no máximo), e posterior escolha do elemento do meio (se houver, dois, tomar o menor).

3: Usar SELECT recursivamente para encontrar a mediana x das ceil(n/5) medianas localizadas na Etapa 2. Se celi(n/5) for par, então x será a mediana inferior.

4: Particionar o arranjo de entrada em torno da mediana de medianas x, em tempo linear. Seja k uma unidade maior que o número de elementos no lado baixo da partição, de forma que x seja o k-ésimo menor elemento e existam n - k elementos no lado alto da partição.

5: Se i = k, então retornar x. Caso contrário, usar SELECT recursivamente para encontrar o i-ésimo menor elemento no lado baixo se i < k, ou então o (i - k)-ésimo menor elemento no lado alto, se i>k.

No processo de obter o 2° menor elemento do arranjo:

 <3,1,2,6,9,10,15,4,5,8,7,13,12>,

indique quais são as medianas encontradas na Etapa 2, depois da primeira chamada recursiva do algoritmo SELECT na Etapa 5:

a) 4 e 2

b) 5 e 3

c) 6 e 2

d) 8 e 3

e) NDA

Ideia original de: Marleny Luque Carbajal