Problema da ordenação:

 - Considere um vetor v de inteiros com n elementos.

 - Dizemos que ele está em ordem crescente se v[0] <= v[1] <= ... <= v[n-1].

 - Um algoritmo para este problema deve rearranjar (permutar) os elementos de v de modo a torná-lo crescente.



Hoje vamos projetar e analisar três algoritmos iterativos básicos para ordenação.

Para cada um destes veremos:

 - Ideia e pseudocódigo, 

 - Invariante e corretude, 

    - Prova por indução no número de iterações
	
	  Base: invariantes devem valer no início da primeira iteração
	  
	  H.I.: supomos que os invariantes valem no início da iteração k
	  
	  Passo: mostramos que eles continuam valendo no início da iteração k+1
	
	- O fato deles valerem quando o algoritmo sai do laço deve implicar o resultado desejado. Neste caso, tal resultado é que o vetor está ordenado.

 - Eficiência no melhor e pior casos, 

 - Estabilidade: 

    - Se o algoritmo não inverte valores identicos no vetor. 

 - In place: 

    - Se o algoritmo não usa estruturas auxiliares proporcionais ao tamanho da entrada. 

 - Supondo uma máquina de 10GHz, ou seja, que executa 10^10 operações por segundo

		n   		n^2  		t(s)
		10  		100  		10^-8
		100 		10^4		10^-6
		1000		10^6		10^-4
		10^6		10^12		10^2
		10^9		10^18		10^8 ~= 3.17 anos