Algoritmo de mediana e indice remissivo

Centro Federal de Educação Tecnológica de Minas Gerais
Laboratório de Algoritmos e Estruturas de Dados I

Prática 1: O objetivo dessa prática é fazer o cálculo da mediana entre três números inteiros. Para fazer esse cálculo utilizamos um algoritmo para determinar a ordem entre os três números informados, dessa a mediana será o número de valor intermediário dessa lista. Entretanto, como o número de entradas é sempre igual a três, não é necessário o uso de uma lista (vetor) para realizar a ordenação dos três números dados. Sejam as três entradas do algorítimo os números inteiros A, B e C. A orenação dos números é dada de acordo com a árvore de decisão abaixo:

Analisando a árvore de decisão do algoritmo podemos observar que, no melhor caso, o algoritmo realiza duas comparações, e em seu pior caso ele realiza três comparações. Desta forma podemos perceber ainda a vantagem desse tipo de implementação (para o caso de três entradas) em relação ao uso de uma lista com um algoritmo de ornedação simples, pois esse tipo de implementação geralmente aprensenta um custo de O(n²) o que leva a um número de comparações três vezes maior do que o pior caso do algorítimo apresentado.

Implementação: public static int CalcularMediana(int n1, int n2, int n3)
{
int intMediana = 0; if(n1 > n2) { if(n2 > n3) intMediana = n2; else { if(n1 > n3) intMediana = n3; else intMediana = n1; } } else { if(n2 > n3) { if(n1 > n3) intMediana = n1; else intMediana = n3; } else intMediana = n2; }

return intMediana;
}

Melhor e pior caso:
Melhor Caso: O(2)
Pior Caso: O(3)

Caso médio:
Para calcular o caso médio foi feita a medição da frequência do número de comparações para 1000 execuções do algoritmo. Os resultados dessa medição se encotram na tabela abaixo:

Duas Comparações
Três Comparações
334
666 De acordo com a tabela acima podemos perceber que o caso