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
Ideia original de: Marleny Luque Carbajal
