MO417 - Questão para a prova oral

Numero:

Enunciado:

Seja o algoritmo SELECT:

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 n/5 grupos, primeiro através da ordenação por inserção dos elementos de cada grupo (dos quais existem 5 no máximo), e depois escolhendo a mediana da lista ordenada de elementos de grupos.

3: Usar SELECT recursivamente para encontrar a mediana x das n/5 medianas localizadas na Etapa 2. (Se existe um número par de medianas, então, por nossa convenção, x é a mediana inferior.)

4: Particionar o arranjo de entrada em torno da mediana de medianas x, usando uma versão modificada de PARTITION. 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 a 2° estatística de ordem 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) 2 y 6

b) 2 y 4

c) 3 y 5

d) 3 y 8

e) NDA

Ideia original de: Marleny Luque Carbajal