Transformação e Conquista

Transformação e Conquista

Problema da Mediana

Definições
Em estatística e probabilidade, a mediana (medida de tendência central) é um número que caracteriza as observações de uma determinada variável de tal forma que este número, a mediana, de um grupo de dados ordenados separa a metade inferior da amostra, população ou distribuição de probabilidade, da metade superior. Ou seja, metade da população terá valores inferiores ou iguais à mediana e metade da população terá valores superiores ou iguais à mediana.

Cálculo da Mediana: dada uma sequência de N números (devemos ordená-los previamente), se N é ímpar, basta calcularmos (N+1)/2 para encontrar a posição da mediana na sequência. E se N é par, então basta calcularmos a média de dois termos: N/2 e (N+2)/2. Porém, seguindo desta maneira, veremos que este cálculo nos leva a O(n log n) para ser executado.

Então vamos utilizar um exemplo mais genérico, o SELECTION.

Entrada: uma lista de números S, um número K.
Saída: O K-ésimo menor elemento de S.

OBS: caso queiramos calcular a mediana utilizando este problema, basta achar o termo (N+1)/2 caso S tenha um tamanho ímpar, ou calcular os termos (N+2)/2 e N/2 caso S tenha tamanho par.

Assim, utilizaremos um algoritmo já visto em aula para encontrarmos uma solução para o nosso problema: o QuickSort.

QuickSort: possui como base a idéia de "dividir para conquistar". Inicia-se com a escolha de um elemento de uma lista, o pivô. A lista é então rearranjada de forma que todos os elementos maiores que o pivô fiquem de um dos lados do pivô e todos os elementos menores fiquem do outro lado (assim o pivô ficará na sua posição definitiva). Fazendo isto de forma recursiva, conseguimos ordenar toda a lista de elementos, porém este não é nosso foco no momento.
Exemplo:
Imagine a sequência de números: S = {2, 36, 5, 21, 8, 13, 11, 20, 5, 4, 1} Consideremos que o pivô seja o 13, então o vetor acima será dividido em dois sub-vetores: menoresPivo = {2, 5, 8,