No problema da seleção, dado um vetor com n elementos em qualquer ordem, queremos determinar o k-ésimo menor elemento.

 - Este problema generaliza o problema de encontrar a mediana de um vetor.

Podemos resolver este problema reduzindo-o ao problema da ordenação, ou seja, primeiro ordenamos o vetor, depois devolvemos o elemento que terminar na posição k. 

 - Como conhecemos algoritmos de ordenação que levam tempo O(n log n), esta maneira de resolver o problema também tem essa complexidade de tempo.
 
Mas, será que conseguimos fazer melhor que isso? Afinal, ao menos intuitivamente, ordenar parece bem mais trabalhoso do que apenas encontrar o elemento que ocupa uma certa posição.

Como motivação podemos considerar um caso particular deste problema, que é encontrar o mínimo ou o máximo.

 - Nós sabemos fazer isso em tempo linear.
 
Será que conseguimos usar divisão e conquista para resolver o problema da Seleção em tempo linear?

Vamos usar o algoritmo da separação (particione) e a ideia de escolher um pivô aleatoriamente que utilizamos no algoritmo QuickSort.



int escolhaPivo(v, l, r)



int particione(vetor v, int l, int r) {
	
	p = v[l]
	i = l+1;
	para j=l+1 até r
		se v[j] < p
			troque v[i] com v[j]
			i++
	troque v[l] com v[i-1]
	devolva i-1
}



// função que encontra o k-ésimo elemento no subvetor de v começado em l e terminado em r
int selecao(vetor v, int l, int r, int k) {

	if (r = l) return v[l]
	
	escolhaPivo(v, l, r)
	m = particione(v, l, r)
	
	if (k = m) return v[m]
	if (k < m) return selecao(v, l, m-1, k)
	/* k > m */ return selecao(v, m+1, r, k-m)
}

Prova de corretude: Basta aplicar indução matemática, fica como exercício.



Análise de eficiência:

Qual a eficiência de pior caso deste algoritmo? Ou seja, qual o pior tipo de pivô que podemos escolher?

 - R: O menor elemento (ou o maior). Neste caso, a cada chamada recursiva eliminamos apenas um elemento. 
 
 - Assim, no total teremos n chamadas recursivas e o trabalho total realizado seguirá o padrão
 
	n + n-1 + n-2 + n-3 + ... + 2 + 1 = n(n+1)/2 = O(n^2)

 - Mas este caso é bastante raro se escolhermos o pivô aleatoriamente.



Qual a eficiência no melhor caso deste algoritmo? Ou seja, qual o melhor tipo de pivô?

 - R: Se desconsideramos a sorte de escolhermos justamente o k-ésimo elemento como pivô, o melhor tipo de pivô é o que divide o vetor ao meio.
 
 - Neste caso especial teríamos a seguinte recorrência:

	T(n) = T(n/2) + O(n)

 - Lembrando do Teorema mestre:

	T(n) = a T(n/b) + O(n^d)

	1) a = b^d --> T(n) = O(n^d log n)

	2) a < b^d --> T(n) = O(n^d)

	3) a > b^d --> T(n) = O(n^log_b a)

 - No melhor caso nosso algoritmo teria complexidade de tempo O(n), ou seja, linear no tamanho da entrada.



Qual a eficiência no caso esperado para este algoritmo?

 - Vamos definir o conceito de fases
 
 - Dizemos que o algoritmo selecao está na fase j se o vetor com o qual ele está lidando tem tamanho tam <= n*(3/4)^j e tam > n*(3/4)^(j+1).
 
 - Assim, no início o algoritmo está na fase 0.
 
 - Seja X_j o número de chamadas recursivas realizadas pelo algoritmo selecao durante a fase j.
 
 - Digamos que o trabalho não recursivo que o algoritmo selecao faz é <= c * tamanho atual do vetor, onde c é uma constante que vem do algoritmo particione.
 
 - Assim, podemos contabilizar o trabalho total realizado pelo algoritmo selecao como 
 
	T(n) <= \sum_{j \in fases} X_j * c * tamanho atual do vetor na fase j <= \sum_{j \in fases} X_j * c * n*(3/4)^j 
 
 - Definimos um bom pivô como aquele que gera uma partição do tipo 25-75%, 
 
    - ou seja, que quebra o vetor corrente em dois de forma que nenhum é menor que 25% e nenhum é maior que 75% 
	
	- note que metade dos elementos do vetor corrente são bons pivôs 
	
	   - ou seja, a probabilidade de escolher um bom pivô aleatoriamente é 50% = 1/2

 - Agora, considere a variável geométrica Y com probabilidade de sucesso igual a 1/2 

    - Variável geométrica é aquela que contabiliza o número de lances de uma "moeda" com probabilidade de sucesso p até obter o primeiro sucesso

    - A esperança de uma variável geométrica é 1/p.
 
    - No caso em que p=1/2 a esperança dessa variável é 2.
	
		E[Y] = 1 + 1/2*E[Y]
		E[Y] - 1/2*E[Y] = 1
		1/2E[Y] = 1
		E[Y] = 2

 - Note que uma fase sempre termina quando um pivô bom é escolhido
 
 - E que a probabilidade de um pivô bom ser escolhido é 1/2
 
 - Assim, a variável Y é um limitante superior para o valor de uma variável X_j qualquer
 
    - Por que superior? R: Porque uma fase também pode terminar com uma divisão ruim. Como?
 
    - Portanto, E[X_j] <= E[Y] = 2

 - Voltando a nossa equação principal do tempo de execução
 
	E[T(n)] <= E[c*n \sum_{j \in fases} X_j (3/4)^j]
			<= c*n \sum_{j=0^+\inf} E[X_j] (3/4)^j (usando linearidade da esperança)
			<= c*n \sum_{j=0^+\inf} 2 (3/4)^j
			<= 2*c*n \sum_{j=0^+\inf} (3/4)^j
			<= 2*c*n 1/(1-(3/4))
			= 2*c*n 4/(4-3)
			= 8*c*n = O(n)