Algoritmos de ordenação

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

UNIVERSIDADE FEDERAL DO VALE DO SÃO FRANCISCO
CAMPUS - JUAZEIRO
ALLISSON PIERRE LINO GOMES
CAROLINE CARVALHO MACHADO
ESRON DTAMAR DA SILVA
PEDRO HENRIQUE DUARTE SANTANA
COMPLEXIDADE DE TEMPO E ESPAÇO DE UM ALGORITMO DE ORDENAÇÃO
JUAZEIRO - BAHIA
2013
ALLISSON PIERRE LINO GOMES
CAROLINE CARVALHO MACHADO
ESRON DTAMAR DA SILVA
PEDRO HENRIQUE DUARTE SANTANA
COMPLEXIDADE DE TEMPO E ESPAÇO DE UM ALGORITMO DE ORDENAÇÃO
Projeto apresentado como requisito para avaliação da disciplina Estrutura de Dados II, do curso de Engenharia de Computação, solicitado pela professora Ana Emilia de Melo Queiroz.
JUAZEIRO - BAHIA
2013
SUMÁRIO
1 INTRODUÇÃO___________________________________________________________3
2 ESQUEMA BÁSICO DE UM ALGORITMO DE ORDENAÇÃO_________________4
3 TAMANHO DE ENTRADA ________________________________________________6
4 TEMPO DE COMPLEXIDADE DE UM ALGORITMO ________________________6
5 ANÁLISE DOS ALGORITMOS_____________________________________________8
5.1 Bubble Sort ________________________________________________________8
5.2 Selection Sort______________________________________________________14
5.3 Insertion Sort _____________________________________________________16
5.4 Shellsort__________________________________________________________20
5.5 Quicksort_________________________________________________________24
5.6 Mergesort ________________________________________________________30
5.7 Heapsort _________________________________________________________36
6 ESPAÇO DE COMPLEXIDADE DE UM ALGORITMO______________________40
7 CONCLUSÃO___________________________________________________________41
REFERÊNCIAS BIBLIOGRÁFICAS ________________________________________42
1 INTRODUÇÃO
Os algoritmos são o objeto central de estudo em muitas áreas da ciência da computação. Vários autores fazem sua própria definição de algoritmo. De acordo com Cormen, algoritmo é um procedimento computacional que toma valores ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída. Dessa forma um conceito geral para algoritmo seria a sequência de passos computacionais que transformam a entrada em saída. (CORMEN et al, 2002)
De forma semelhante, Ziviani (2004) afirma que “Algoritmo pode ser visto como uma sequência de ações executáveis para obtenção de uma solução para um determinado tipo de problema”. Já Sedgewick (1998) define algoritmos na área da ciência da computação como um método para resolução de problemas, adequado para implementação como um programa de computador.
Na resolução de problemas de computação é necessário definir um conjunto de dados adequado para organizar os dados envolvidos no cálculo. Essa representação dos dados, chamada de estrutura de dados, é determinada a partir das operações que serão realizadas, dependendo do seu contexto. Assim, “estruturas de dados são subprodutos ou produtos finais de algoritmos para organizar os dados envolvidos no cálculo”. (SEDGEWICK, 1998)
Dado determinado problema, há uma série de possíveis abordagens diferentes. Assim, torna-se necessária a realização de uma análise da complexidade para verificar qual método utiliza o tempo e o espaço da melhor maneira possível. São feitas duas análises, uma sobre o tempo de complexidade de um algoritmo, e outra sobre o espaço de complexidade de um algoritmo.
Pode-se realizar a análise de um algoritmo particular, na qual se verifica o custo de um determinado algoritmo na resolução do problema. Para isso, características importantes do algoritmo em questão devem ser investigadas, geralmente uma análise do número de vezes que cada parte do algoritmo deve ser executada, seguida do estudo da quantidade de memória necessária.
Também é possível fazer a análise de uma classe de algoritmos, na qual se verifica qual é o algoritmo de menor custo possível para resolver um problema. Para isso, toda uma classe de algoritmos é estudada com o objetivo de identificar um que seja o melhor possível. Isso significa colocar limites para a complexidade computacional dos algoritmos pertencentes à classe.
O objetivo desse projeto é realizar a análise da complexidade de uma classe de algoritmos, os algoritmos de ordenação, e descrever a sua eficiência. Foram analisados os algoritmos do bubble sort, insertion sort, selection sort, shellsort, quicksort, mergesort e heapsort. Mas antes de realizar essa análise é necessário abordar alguns conceitos necessários para a compreensão do estudo da complexidade.
2 ESQUEMA BÁSICO DE UM ALGORITMO DE ORDENAÇÃO
Os algoritmos que serão analisados realizam a operação de ordenação. Ziviani (2004) define o método de ordenação como o “Processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente. O objetivo principal da ordenação é facilitar recuperação posterior de itens do conjunto ordenado”. Todos os métodos seguem um esquema básico de funcionamento, variando apenas a forma como realizam as operações. A seguir, será descrito o processo básico de um algoritmo de ordenação, definindo seus elementos comuns.
Tenenbaum descreve a essência do método de ordenação. Um arquivo de tamanho n é uma sequência de n itens r[0], r[1],..., r[n-1]. Cada item no arquivo é chamado registro. Uma chave k[i] é associada a cada registro r[i]. A chave é geralmente (mas nem sempre) um subcampo do registro. Diz-se que o arquivo está classificado pela chave se i < j implicar que k[i] precede k[j] em alguma classificação nas chaves. (TENENBAUM, 1995)
A escolha do tipo para a chave é arbitrária, desde que exista uma regra de ordenação bem definida possa ser utilizada. As ordens numéricas e alfabéticas são as mais comuns. Na figura 1 abaixo pode ser visto o esquema básico de um algoritmo de ordenação.
Figura 1: Esquema básico de um algoritmo de ordenação.
Todo algoritmo de ordenação deve realizar as seguintes tarefas: receber os dados para poderem ser ordenados, comparar os elementos dos dados que estabelecerão a ordem e verificar a necessidade de realizar a troca para se chegar à ordem.
Entre os algoritmos de ordenação existem algumas características básicas que separam os métodos em subclasses. Existem os algoritmos elementares (insertion, selection, bubble...) chamados assim devido a sua fácil implementação, geralmente eles possuem uma complexidade de tempo maior, e uma complexidade de espaço menor. Outra subclasse não os algoritmos sofisticados (quicksort, mergesort...), possuem códigos maiores e mais complexos, geralmente consomem menos tempo e mais espaço que os métodos elementares.
Também é possível classificar os algoritmos em ordenação interna e externa. Os algoritmos de ordenação interna consomem apenas a memória primária para realizar a ordenação. O método externo usa memória externa, secundária, já que o arquivo é muito grande para caber na memória principal.
Ziviani (2004) descreve três fatores que tornam os algoritmos de ordenação externa bastante diferente dos de ordenação interna, são eles:
O custo para acessar um item é algumas ordens de grandeza maior do que os custos de processamento na memória interna. O custo principal está na transferência de dados entre a memória interna e externa.
Existem restrições severas de acesso aos dados. Por exemplo, os itens só podem ser acessados em ordem sequencial, já que o acesso direto possui um custo muito maior do que o acesso sequencial.
O desenvolvimento de métodos de ordenação externa é muito dependente do estado atual da tecnologia.
Por fim, os algoritmos de ordenação podem ser classificados pela sua estabilidade. Tenenbaum descreve a estabilidade para dois registros num arquivo que tenham a mesma chave. Uma técnica de classificação é chamada estável se, para todos os registros i e j, k[i] seja igual a k[j]; se r[i] precede r[j] no arquivo original, r[i] precederá r[j] no arquivo classificado, ou seja, uma classificação
estável mantém os registros com a mesma chave na mesma ordem relativa em que estavam antes da classificação (TENENBAUM, 1995). A maioria dos algoritmos elementares são estáveis e muitos dos sofisticados não são. Pouco dos métodos sofisticados alcança a estabilidade sem usar uma significativa quantidade de tempo e espaço extra.
3 TAMANHO DE ENTRADA
Para algoritmos de ordenação, o tamanho de entrada (n) influencia muito no seu tempo de execução. Para determinar a função de complexidade de tempo, que será analisada mais adiante, termos que desempenham um papel insignificante para grandes valores de n podem desempenhar uma função importantíssima para pequenos valores de n. Por isso é comum considerar-se o tempo de execução de um programa em função do tamanho da entrada. Dependendo do tamanho da entrada do problema, diferentes métodos de ordenação podem ser escolhidos.
Entretanto, para a maioria dos algoritmos de ordenação, o custo de execução depende também da ordem da entrada. Para melhor avaliar os métodos de ordenação, criou-se a convenção do melhor, médio e pior caso para a entrada. O melhor caso é uma entrada de dados que já esteja na ordem desejada. O caso médio, para maiores simplificações, é considerada uma entrada aleatória de dados, sem nenhuma ordem especial. O pior caso é uma entrada de dados na ordem inversa à desejada.
4 TEMPO DE COMPLEXIDADE DE UM ALGORITMO
Antes da realização da análise de cada algoritmo de ordenação é necessário conhecer três dos mais importantes aspectos sobre a eficiência de um algoritmo que inclui o tempo que será gasto pelo programador ao codificar determinado programa de classificação, o tempo da máquina necessário para executar o programa e o espaço necessário para o programa.
Para medir a eficiência de um algoritmo define-se uma função de custo ou função de complexidade f. Se f(n) é a medida da quantidade de tempo necessário para executar um algoritmo em um problema de tamanho n, então f é chamada função de complexidade de tempo do algoritmo. Se f(n) é uma medida de quantidade da memória necessária para executar um algoritmo de tamanho n, então f é chamada função de complexidade do espaço.
Não se define uma função de tempo com base no real tempo de execução de um algoritmo, já que ele varia de uma máquina para outra, a função é determinada com base na variação do tempo em relação ao tamanho do arquivo. Essa variação é proporcional quantidade de operações críticas realizadas, como comparações e trocas, quando n cresce. Assim podem-se ignorar as operações aritméticas, de atribuição e manipulação de índices, caso existam.
Para entender o conceito de uma função tornando-se proporcional a outra à medida que aumenta, analisa-se o comportamento assintótico das funções utilizando a notação O. Ziviani (2004) apresenta as seguintes definições:
Dada duas funções, g(n) e f(n), Uma função g(n) é da ordem de O(f(n)) se existirem duas constantes positivas c e m tais que g(n) ≤cf(n), para todo n≥m.
Uma função f(n) domina assintoticamente outra função g(n) se existem duas constantes positivas c e m tais que, para n >=m, temos |g(n)|<=c x |f(n)|.
Figura 2: Dominação assintótica de f(n) sobre g(n)
O valor de m mostrado é o menor valor possível, mas qualquer outro valor maior também é possível. A tabela 1 a seguir estabelece a hierarquia de ordem de funções, onde cada função é de ordem mais baixa que a seguinte.
Tabela 1: Hierarquia de ordem de funções.
	c é O(1) para toda constante c. Complexidade constante.
	c é O(log n) mas log n não é O(1). Complexidade logarítmica.
	c * logk n é O(log n) para quaisquer constantes c, k.
	c * logk n é O(n) mas n não é O(log n). Complexidade linear.
	c * nk é O(nk) para quaisquer constantes c, k. Complexidade quadrática ou cúbica para k=2 ou k =3. 
	c * nk é O(nk+j), mas nk+j não é O(nk).
	c * n * logk n é O(n log n) para quaisquer constantes c, k.
	c * nj * logk n é O(nj log n) para quaisquer constantes c, j, k.
	c * nj * logk n é O(nj+1), mas nj+1 não é O(nj log n).
	c * nj * (logk n)l é O(nj (logk n)l) para quaisquer constantes c, j, k, l.
	c * nj * (logk n)l é O(nj+1), mas nj+1 não é O(nj (logk n)l).
	c * nk é O(dn), mas dn não é O(nk) para quaisquer constantes c e k, e d>1. Complexidade exponencial.
Usando esse conceito da ordem de uma classificação, podem-se comparar vários métodos e categorizá-los como “eficientes” ou “ineficientes”, em termos gerais.
Para se obter a função do tempo, faz-se a análise do algoritmos nos vários casos. Melhor caso: corresponde ao menor tempo de execução sobre todas as possíveis entradas de tamanho n. Pior caso: corresponde ao maior tempo de execução sobre todas as entradas de tamanho n. O custo nunca é superior ao do pior caso. Caso médio: ou caso esperado, corresponde a média dos tempos de execução de todas as entradas de tamanho n.
Para se obter um algoritmo mais eficiente para determinado problema é necessário conhecer o limite inferior de um problema, que se refere a um resultado teórico que determina qual é a melhor complexidade possível que um algoritmo pode alcançar. Já o limite superior de complexidade refere-se ao melhor algoritmo que o resolve, quando a diferença entre esses limites desaparece, a complexidade mínima do problema é conhecida e o problema é chamado fechado. Quando conseguimos determinar o menor custo possível para resolver problemas de uma determinada classe, como no caso de ordenação, tem-se a medida da dificuldade inerente para resolver o problema.
5 ANÁLISE DOS ALGORITMOS
5.1 Bubble Sort
O bubble sort é um dos métodos de ordenação mais simples existentes. Sua ideia básica é percorrer o arquivo sequencialmente várias vezes, trocando elementos adjacentes que estão fora de ordem, continuando até que o arquivo seja ordenado. O método é chamado de classificação por bolha porque cada elemento “borbulha” lentamente para a posição correta.
O bubble sort pode ser caracterizado como um método de ordenação interno, já que não é necessário buscar dados na memória externa. Ele também é um método estável, já que não altera a ordem de registros com chaves iguais.
Funcionamento
Para os algoritmos apresentados, Item a[ ] é um vetor de inteiros com n elementos que devem ser classificados de modo que a[ j – 1] ≤ a[ j ]. O vetor é percorrido da direita (final) para a esquerda (início).
Cada loop interno do coloca o menor elemento em sua posição fazendo-o “flutuar” até o início. O índice i do loop externo anda da esquerda para a direita no vetor, e os elementos a sua esquerda já estão ordenados, logo nenhuma comparação precisar ser feita com eles, logo o processo se agiliza com sucessivas passagens. As variáveis ncomp, e nexch, são contadores para o número de comparações e trocas, respectivamente.
Abaixo está o programa com a função main onde as rotinas serão inseridas. Todos os algoritmos do bubble sort são baseados nos algoritmos apresentados pelo Sedgewick (1998).
	Programa 1 – Função main
#include <stdio.h>
#include <stdlib.h>
typedef int Item;
#define N 1000
#define key(A) (A)
#define less(A, B) (key(A) < key(B)) //compara as duas chaves
int main()
{
 int i;
 Item a[ N ];
 for( i = 0 ; i < N ; i++)
 a[ i ] = N – i;
 bubble( a, 0, N – 1);
 for( i = 0 ; i < N ; i++)
 printf("%d ", a[ i ]);
 printf("\n");
 scanf("");	
}
Bubble Sort Simples
O bubble sort simples executará N voltas, independentemente de o arquivo estar ordenado antes disso. O bubble sort opera como um selection sort, porém realiza muito mais trabalho para colocar cada elemento em sua posição. O programa 2 mostra o bubble sort simples implementado.
	Programa 2 - Bubble sort simples
void bubble( Item a[ ], int l, int r)
{
 int i, j ;
 int ncomp = 0, nexch = 0;
 for ( i = l ; i < r ; i++ )
 for ( j = r ; j > i ; j-- )
 {
 ncomp++;
 if ( less ( a[ j ], a[ j – 1 ]))
 {
 exch( a[ j – 1 ], a[ j ]);
nexch++; k=1;
 }
 };
 printf ( "Numero de comparacoes %d \nNumero de trocas %d \n \n", ncomp, nexch);
}
Bubble Sort Aprimorado
Um modo de aprimorar o bubble sort é detectando passagens desnecessárias, encerrando o programa quando o arquivo estiver ordenado. Para isso basta colocar um registro da ocorrência de trocas (variável k), quando ele for 0, o loop se encerra. Esse método melhora a execução para arquivos parcial ou totalmente ordenados e é apresentado no programa 3.
	Programa 3 – Bubble sort aprimorado
void bubble( Item a[ ], int l, int r)
{
 int i, j ;
 int ncomp = 0, nexch = 0, k = 1;
 for ( i = l ; i < r && k == 1; i++ )
 {
 k = 0;
 for ( j = r ; j > i ; j-- )
 {
 ncomp++;
 if ( less ( a[ j ], a[ j – 1 ]))
 {
 exch( a[ j – 1 ], a[ j ]);
 nexch++;
 k=1;
 }
 }
 }
 printf ("Numero de comparacoes %d \nNumero de trocas %d \n \n", ncomp, nexch);
}
Análise
Para uma implementação do bubble sort que não inclua aprimoramentos análise é simples. Existem (n – 1) passagens e (n – 1), (n – 2), (n – 3)... comparações em cada passagem o que resulta em uma função de ordem O(n²). O número de trocas depende da sequência inicial do arquivo, mas não pode ser maior que o número de comparações.
Em um blubble sort aprimorado o número de comparações na iteração i é n – i, se existirem k iterações, o número total de iterações será (n-1)+(n-2)+(n-3)+ ... + (n-k), que é igual a (2kn - k² - k)/2. O número médio de iterações é O(n), de modo que a fórmula inteira ainda é O(n²).
Abaixo é apresentada a análise empírica de ambos os bubble sort apresentados.
	Análise Empírica do Bubble Sort Simples
	Esta análise se refere ao algoritmo do Programa 2.
	N
	Melhor
	Médio
	Pior
	
	ncomp
	nexch
	ncomp
	nexch
	Ncomp
	nexch
	1000
	499500
	0
	499500
	253384
	499500
	499500
	2000
	1999000
	0
	1999000
	976988
	1999000
	1999000
	4000
	7998000
	0
	7998000
	3995026
	7998000
	7998000
	8000
	31996000
	0
	31996000
	15879191
	31996000
	31996000
	16000
	127992000
	0
	127992000
	63615324
	127992000
	127992000
	Melhor
	O melhor caso é dado por um vetor ordenado
	Médio
	O médio caso é dado por um vetor aleatório
	Pior
	O pior caso é dado por um vetor de ordem inversa
	ncomp
	Contador para o número de comparações
	nexch
	Contador para o número de trocas
	
	
	Análise Empírica do Bubble Sort Aprimorado
	Esta análise se refere ao algoritmo do Programa 3.
	N
	Melhor
	Médio
	Pior
	
	ncomp
	nexch
	ncomp
	nexch
	ncomp
	nexch
	1000
	999
	0
	499310
	253384
	499500
	499500
	2000
	1999
	0
	1997289
	976988
	1999000
	1999000
	4000
	3999
	0
	7995654
	3995026
	7998000
	7998000
	8000
	7999
	0
	31986684
	15879191
	31996000
	31996000
	16000
	15999
	0
	127977294
	63615324
	127992000
	127992000
	Melhor
	O melhor caso é dado por um vetor ordenado
	Médio
	O médio caso é dado por um vetor aleatório
	Pior
	O pior caso é dado por um vetor de ordem inversa
	ncomp
	Contador para o número de comparações
	nexch
	Contador para o número de trocas
	
Com os dados obtidos, é possível observar para o bubble simples e para o médio e pior caso do bubble aprimorado que quando N duplica, o número de comparações e trocas realizadas quadruplica, refletindo a sua ordem crescimento de O(n²).
Melhor caso
No melhor caso é onde melhor se observa a diferença entre as duas implementações do bubble sort. Na versão simples a ordem de crescimento para o número de comparações é O(n²), enquanto que na versão aprimorada o crescimento é da ordem de O(n), onde apenas uma passagem é necessária para verificar a ordenação do vetor.
Abaixo é apresentado o gráfico para o melhor caso comparando o número de comparações realizadas entre ambos os métodos.
Médio caso
A diferença entre os métodos se torna insignificante no médio caso. É possível observar que para ambos os métodos, o número de comparações pode ser dado por aproximadamente N²/2, enquanto que o número de trocas pode ser dado por N²/4. Observa-se também que ambas as funções são de ordem O(n²).
A seguir é apresentado o gráfico para o médio caso comparando o número de comparações e trocas realizadas entre ambos os métodos. A linha azul é sobreposta pela vermelha e a verde é sobreposta pela roxa, justamente devido à diferença insignificante entre os métodos dada pela constante de proporcionalidade.
Pior caso
Não há diferença entre os métodos para o pior caso, ambos realizarão cerca de N²/2 comparações e N²/2 trocas. Para o pior caso o bubble sort se revela muito lento, principalmente para grandes valores de N, logo, deve-se evitar usar o bubble nesses casos.
O gráfico abaixo mostra o número de comparações e o número de trocas realizado pelo bubble sort, a linha azul (ncomp) é sobreposta pela linha vermelha (nexch) já que não há diferenças entre elas.
As principais vantagens do bubble sort são a exigência de pouco espaço adicional, é necessário apenas um registro para armazenar o valor da troca e os índices do vetor. Outra vantagem é o fato dele ser O(n) para um arquivo praticamente ordenado, isso se verifica que apenas uma passagem de (n – 1) comparações (e nenhuma troca) é necessária para perceber que o arquivo está ordenado. O bubble sort também possui uma fácil implementação, mas não pode se afirmar com certeza que ele é mais fácil de implementar que o insertion ou selection.
Uma ocorrência comum nas aplicações é modificar um arquivo já ordenado, adicionando uma chave ou modificando o valor de uma já existente, para esse tipo de situação não se deve usar o bubble ou o selection, o insertion sort é o método mais adequado.
Existem outros métodos de aprimorar bubble sort. Um deles agiliza o método fazendo com que as passagens sucessivas percorram o vetor em direções opostas, de modo que os pequenos elementos se desloquem mais rapidamente para o início do arquivo da mesma forma que os grandes se deslocam para o final, o que reduz o número necessário de passagens.
5.2 Selection Sort
	O método de ordenação Selection Sort é considerado simples, pois é adequado para pequenos arquivos que requerem a ordem de n2 de comparações para a ordenação, sendo 'n' o tamanho do arquivo. O funcionamento deste algoritmo, consisti em selecionar o menor item de um determinado vetor e em seguida trocá-lo com o item que está na posição inicial do vetor, esse processo se repete até que todos os itens estejam ordenados. Abaixo o algoritmo do Selection Sort implementado, de acordo com Ziviani (2004):
	Programa 4 – Selection Sort
#include <stdio.h>
#define N 1000
typedef int Item;
void selection (int vet[], int n)
{
	int min, i, j, comp=0, troc=0; Item aux;
	for (i=0; i<n-1; i++)
	{ min=i;
		for (j=i+1; j<n;j++){
			if (vet[j]<vet[min]) min=j; comp++;}
		aux = vet[i];
		vet[i]=vet[min];
		vet[min]= aux; troc++;
	}
	For (i=0; i<n; i++) {printf (“%d “, vet[i]);}
	printf (“\nComparacoes: %d \nTrocas: %d”, comp, troc);
}
int main ()
{
	int v[N], I;
	for (i=0; i<N; i++)
	 v[i] = N – I;
	
 selection (v, N);
	scanf (“”);
	return 0;
}
	
Analisando esse algoritmo, vê-se que quando ele entra no segundo for aliado ao if, ocorre a verificação do menor valor percorrendo-se o vetor (vet[]), após encontrar este valor, que ficará guardado em vet[min], ele sai do segundo for para ser trocado com o valor da posição inicial (vet[i]) com o auxílio do aux, isso ocorre até que todos os valores sejam organizados. 
Como nesse mecanismo se utiliza apenas o próprio vetor para a organização dos itens, então não há a utilização de uma quantidade extra de memória, ou seja, há uma economia de memória, que é um aspecto importante em uma ordenação interna. A seguir é apresentada uma tabela com o desempenho do Selection Sort:
Tabela
1: Número de trocas e comparações para determinadas entradas.
	Análise Empírica do Selection Sort
	Esta análise se refere ao algoritmo do Programa 4.
	N
	Melhor
	Médio
	Pior
	
	comp
	troc
	comp
	troc
	comp
	troc
	1000
	499500
	999
	499500
	999
	499500
	999
	2000
	1999000
	1999
	1999000
	1999
	1999000
	1999
	4000
	7998000
	3999
	7998000
	3999
	7998000
	3999
	8000
	31996000
	7999
	31996000
	7999
	31996000
	7999
	16000
	127992000
	15999
	127992000
	15999
	127992000
	15999
	Melhor
	O melhor caso é dado por um vetor ordenado
	Médio
	O médio caso é dado por um vetor aleatório
	Pior
	O pior caso é dado por um vetor de ordem inversa
	comp
	Contador para o número de comparações
	troc
	Contador para o número de trocas
	Examinando o algoritmo e a tabela acima, o Selection Sort em seu pior, médio, ou melhor caso, terá de qualquer forma o mesmo número de trocas (N-1) e o mesmo número de comparações, que é dado por N(N-1)/2. Ele tem como um ponto negativo ser instável, já que nem sempre deixa registros com valores iguais na mesma posição relativa. 
Gráfico: Movimentações Selection Sort.
	
	
	
	
	
	
Independente de sua entrada, o Selection Sort tem um comportamento linear quanto ao número de movimentos de itens, ou seja, independente de estar ordenado ou não, ele percorrerá todo o vetor e fará trocas mesmo estando ordenado. Por essas razões, é aconselhável utilizá-lo para arquivos com poucos registros, em caso de arquivos maiores existem outros métodos de ordenação mais sofisticados apresentam um desempenho melhor.
5.3 Insertion Sort
	O processo utilizado para ordenação através do Insertion Sort também é classificado como simples, mas diferente do Bubble Sort e do Selection Sort, essa técnica de rearranjo de dados tem número de comparações dependendo da organização inicial de determinada lista de itens e é também considerada estável.
	O funcionamento do Insertion Sort acontece através de um vetor, em que se considera dois segmentos do mesmo, um ordenado e outro não, e retira-se um elemento por vez do sub-vetor não ordenado, para inseri-lo na posição correta dentro do sub-vetor ordenado, isso ocorre até que o vetor fique totalmente organizado.
	A seguir, pode-se ver o algoritmo Insertion Sort implementado, de acordo com Ziviane (2004).
	Programa 5 – Insertion Sort
#include <stdio.h>
#define N 1000
typedef int Item;
void insertion (int vet[], int n)
{
	int i, j, min, comp=0, troc=0;
	Item aux;
	for (i=1; i<n; i++)
	{
		aux=vet[i]; j=i-1;
		vet[-1]=aux; /* Sentinela */
		while (aux < vet[j])
		{
			vet[j+1]= vet[j]; j--; comp++; troc++;
		}
		if (aux >= vet[j] && 0<j+1)
	 		comp++;
		vet[j+1]= aux;
	}
	for(i=0; i<n; i++)
		printf ("%d ", vet[i]);
	printf ("\n\nComparacoes:%d \nTrocas: %d", comp, troc);	
}
int main()
{
	int v[N], i;
	for (i=0; i<N; i++)
		v[i]= N-i;
	insertion(v, N);
	scanf ("");
	return 0;
}
	
Nesse algoritmo pode-se vê que o Insetion Sort percorre o vetor da esquerda pra direita, para ordenar a posição, que está no primeiro for, em relação aos demais valores a sua esquerda, ou seja, caso o valor da posição que está passando seja menor que o da posição anterior, ele faz a troca, essa comparação é usada também como critério de parada do while.
	O Insertion Sort ainda pode ser implementado com uma busca binária, otimizando sua forma de ordenação, pois diminui o número de comparações utilizando-se de um processo parecido com o da busca em uma Árvore de Pesquisa Binária, onde cada comparação feita elimina várias outras que seriam desnecessárias, consequentemente melhorando de maneira geral o desempenho do algoritmo.
	Análise Empírica do Insertion Sort
	Esta análise se refere ao algoritmo do Programa 5.
	N
	Melhor
	Médio
	Pior
	
	comp
	troc
	comp
	Troc
	comp
	troc
	1000
	999
	0
	256322
	255326
	499500
	499500
	2000
	1999
	0
	1042642
	1040648
	1999000
	1999000
	4000
	3999
	0
	3935655
	3931667
	7998000
	7998000
	8000
	7999
	0
	15782854
	15774862
	31996000
	31996000
	16000
	15999
	0
	64175703
	64159718
	127992000
	127992000
	Melhor
	O melhor caso é dado por um vetor ordenado
	Médio
	O médio caso é dado por um vetor aleatório
	Pior
	O pior caso é dado por um vetor de ordem inversa
	comp
	Contador para o número de comparações
	Troc
	Contador para o número de trocas
	
Com base na tabela acima, vê-se que o Insertion Sort é mais eficiente dentre os métodos mais simples de ordenação, por exemplo, em comparação com o Selection Sort e com o Bubble Sort, quando recebe um vetor ordenado, ou parcialmente ordenado, realizada menos comparações e trocas do que os outros dois.
	Abaixo os gráficos com as comparações e trocas de cada caso do Insertion:
No melhor caso, em que o vetor inicial já está ordenado, o Insertion apresenta uma função linear com relação ao número de comparações (N-1), e como já está organizado, ele não realiza trocas entre os itens do determinado vetor, neste caso a sua eficiência, que está relacionada com essas comparações e trocas tem sua complexidade de tempo na ordem N.
	
Em seu caso médio o Insertion usa cerca de N²/4 comparações e N²/4 deslocamentos, ainda assim pode ser considerado melhor do que as outras técnicas que apresentam complexidade de ordem N².
Em seu pior caso, seu funcionamento apresenta complexidade de ordem N², igualando-se aos outros métodos simples de ordenação, ou seja, neste caso não há vantagens consideráveis sobre os demais métodos elementares.
	Como visto, o Insertion Sort se torna vantajoso, quando o vetor de entrada já tem seus valores ordenados, ou parcialmente ordenados, pois realiza menos trocas e comparações, fazendo com que sua complexidade de tempo seja de N, tornando-se assim um método eficiente sobre as demais técnicas ordenações simples.
5.4 Shellsort
O shellsort foi criado como uma extensão do insertion sort, também é conhecido como método de classificação de implemento decrescente. Principal característica é ganhar velocidade permitindo a troca de elementos que estão distantes, o que o insertion não pode fazer. Sua ideia básica é classificar subarquivos independentes do arquivo original sem utilizar memória extra.
O shellsort pode ser caracterizado como um método de ordenação interno, já que não é necessário buscar dados na memória externa. O método não é estável, pois ele nem sempre deixa registros com chaves iguais na mesma posição relativa.
O shelllsort funciona baseado em uma sequência de incrementos h, a sequência de incremento utilizada aqui 1 4 13 40 121 364 1093 3280 9841..., onde cada incremento h é 1/3 do incremento posterior. Sendo de fácil implementação (começa com 1, gerando o próximo incremento multiplicando por 3 e adicionando 1) e conduz para uma ordenação relativamente eficiente, mesmo para arquivos relativamente largos, esta sequência é difícil de ser batida por mais de 20% em eficiência no tempo de execução. (ZIVIANI, 2004)
Os subarquivos são os h-ésimos elementos do vetor a[ ], por exemplo, para h = 4, tem-se os subarquivos intercalados (0 4 8)(1 5 9)(2 6 10)(3 7 11), cada um deles será ordenado por inserção simples, depois disso será escolhido um valor menor de h na sequência, gerando um novo subarquivo que será classificado e assim sucessivamente. Por fim o valor de h será 1 (obrigatoriamente em qualquer sequência), o arquivo inteiro será classificado correspondendo ao insertion sort, entretanto nenhum item tem que se mover para posições muito distantes.
Para cada h, usa-se o insertion sort independentemente em cada subarquivo h, inserindo o movendo o menor elemento para a esquerda do subarquivo h. Esta tarefa é realizada usando o código do insertion sort modificado para incrementar ou decrementar por h ao invés de 1 quando se move pelo arquivo. O shellsort utilizado calcula o próximo incremento dividindo o
atual por 3, após a inicialização para garantir para garantir que a mesma sequência é sempre usada.
Como o primeiro incremento usado pelo shell é grande, os subarquivos são pequenos e as classificações velozes. Cada passo faz com que o arquivo esteja mais próximo da ordenação. Com o passar das classificações os subarquivos posteriores já estarão praticamente ordenados o que torna suas classificações mais eficientes. É importante observar que se um arquivo é parcialmente classificado usando um incremento h e, em seguida é parcialmente classificado usando um incremento j, o arquivo permanece parcialmente classificado pelo incremento h, ou seja, as classificações parciais subsequentes não prejudicam as anteriores.
Abaixo está o programa com a função shellsort baseado no algoritmo apresentado pelo Sedgewick (1998).
	Programa 6 – Shellsort (1 4 13 40 121 364 1093 3280 9841...)
#include <stdio.h>
#include <stdlib.h>
typedef int Item;
#define N 1000
void shellsort( Item a, int size)
{
 int nexch = 0, ncomp = 0;
 int i , j , value;
 int h = 1;
 while(h < size)
 h = 3*h+1;
 while ( h > 1)
 {
 h /= 3;
 for(i = h; i < size; i++, ncomp++ )
 {
 value = vet[i];
 j = i - h;
 while (j >= 0 && value < vet[j])
 {
 ncomp++;
 nexch++;
 vet [j + h] = vet[j];
 j -= h;
 }
 vet [j + h] = value;
 }
 }
 printf("Numero de comparacoes %d\nNumero de trocas %d\n\n", ncomp, nexch);
}
int main()
{
 int i;
 Item a[N];
 for( i = 0; i < N; i++)
 a[ i ] = N – i;
 shellsort(a, N);
 for( i = 0 ; i < N ; i++)
 printf("%d ", a[ i ]);
 printf("\n");
 scanf("");
}
Considerações sobre as sequências
Ainda não foi encontrada a melhor sequência de incrementos a ser usada. Uma boa sequência de incremento aumenta a velocidade de execução do programa, mas esse aumento é limitado por cerca de 25%. Este problema apresenta um bom exemplo da complexidade inerente de um algoritmo aparentemente simples.
Uma sequência melhor do que a utilizada é 1 8 23 77 281 1073 4193 16577, que tem o comportamento mais rápido para o pior caso. A possibilidade de que exista uma sequência melhor ainda é real. Por outro lado há sequências muito ruins, por exemplo, 1 2 4 8 16 32 64 128 256... (a sequência originalmente sugerida para o shell) conduz para um péssimo desempenho porque elementos em posições ímpares não são comparados com elementos das posições pares até o último passo.
Análise
A descrição da eficiência do shellsort é necessariamente imprecisa, já que ninguém conseguiu a analisar o algoritmo, nem sequer a forma funcional do tempo de execução do shellsort é conhecida e a função depende da sequência de incremento. A sua análise contém alguns problemas matemáticos muito difíceis.
A ordem do shellsort é de O(nk), onde k vai diminuindo a medida que o tamanho do arquivo aumenta, além disso o tempo de execução é sensível a ordem inicial do arquivo.
	
Análise Empírica do Shellsort
	Esta análise se refere ao algoritmo do Programa 6.
	N
	Melhor
	Médio
	Pior
	
	ncomp
	nexch
	ncomp
	nexch
	ncomp
	nexch
	1000
	5457
	0
	13504
	8047
	9377
	3920
	2000
	12364
	0
	32063
	19699
	19648
	7284
	4000
	27084
	0
	74871
	47787
	46380
	19296
	8000
	59084
	0
	182262
	123178
	98878
	39794
	16000
	129243
	0
	456880
	327637
	212279
	83036
	Melhor
	O melhor caso é dado por um vetor ordenado
	Médio
	O médio caso é dado por um vetor aleatório
	Pior
	O pior caso é dado por um vetor de ordem inversa
	ncomp
	Contador para o número de comparações
	nexch
	Contador para o número de trocas
	
Melhor caso
Para o melhor caso, k é 1.25 e a ordem é de O(n1.25), ao aumentar o tamanho do vetor k diminui, para N = 16000, k é próximo de 1.22. Abaixo é apresentado o gráfico para o melhor caso apresentando o número de comparações e trocas realizadas.
Médio caso
O médio caso do shellsort acaba realizando mais operações que o pior caso, pois sua ordenação é mais complicada. A ordem é de O(n1.38) para o número de comparações e O(n1.31) para trocas e vai diminuindo com o aumento do vetor. Abaixo é apresentado o gráfico para o melhor caso apresentando o número de comparações e trocas realizadas.
Pior caso
Para um vetor na ordem inversa, a ordem é de O(n1.33) para comparações e O(n1.20) para trocas e vai diminuindo com o aumento do vetor. Abaixo é apresentado o gráfico para o melhor caso apresentando o número de comparações e trocas realizadas.
O shellsort é uma ótima opção para arquivos de tamanho moderado, até porque sua implementação é simples e requer uma quantidade de código pequena. Existem métodos de ordenação mais eficientes, mas são mais complicados de implementar. O shellsort é um método prático até para grandes arquivos, diferente do selection, insertion e bubble sort.
Uma técnica semelhante ao shell pode ser utilizada para aprimorar o bubble. Se uma sequência de incrementos for usada para definir subarquivos individuais o bubble, as classificações iniciais ocorrerão sobre subarquivos pequenos e as posteriores sobre arquivos praticamente classificados, onde serão necessárias poucas trocas. Esse aprimoramento exige pouca sobrecarga e funciona bem em situações práticas.
5.5 Quicksort
O quicksort é um dos algoritmos de ordenação mais rápidos que se conhece, usado em diversas situações e sendo mais usado que qualquer outro algoritmo de ordenação. Nesse algoritmo de ordenação usa-se o paradigma dividir para conquistar, dividindo um problema n em dois problemas n menores. Após solucionar os subproblemas menores seus resultados são combinados produzindo a solução do problema maior. 
Em sua execução a parte mais delicada é o procedimento de Partição, o qual escolher um determinado pivô e rearranja o vetor em dois grupos, um grupo de elementos menores ou iguais ao pivô e um segundo de maiores ou iguais, essa parte do algoritmo seria a parte de dividir, onde um dos fatores importantes para uma boa divisão é a escolha do pivô (Ziviani, 2004). Após isso, é executada a parte de conquistar, onde os dois subarranjos são ordenados e chamados recursivamente. Por ultimo, o passo chamado de combinar, onde esses subarranjos são ordenados localmente não sendo necessário nenhum trabalho. 
A parte que faz com que o quicksort seja tão eficiente para ordenação é o particionamento, entrando com um vetor de limite inferior “A”, um limite superior “r” e o pivô “p”. Após a escolha do pivô duas variáveis iram se deslocar pelo vetor, entrando no loop se a condição for verdadeira, como por exemplo, se a chave for menor que o pivô. Verificada todas as condições são feitas as trocas até que percorra todo o vetor e assim colocando o pivô no seu local ordenado no vetor. (CORMEN et al, 2002) 
Em seguida é mostrado o código do quicksort em C junto com função main onde as rotinas serão inseridas. As variáveis ncomp, e nexch, são contadores para o número de comparações e trocas, respectivamente.
	Programa 7 – Quicksort
#include <stdio.h>
#include <stdlib.h>
typedef int Item;
#define N 10
int ncomp = 0, nexch = 0;
void swap(int* a, int* b)
{
 int tmp;
 tmp = *a;
 *a = *b;
 *b = tmp;
}
int partition(int vec[], int left, int right)
{
 int i, j;
 i = left;
 for (j = left + 1; j <= right; ++j)
 {
 ncomp = ncomp+1;
 if (vec[j] < vec[left])
 {
 ++i;
 swap(&vec[i], &vec[j]);
 nexch = nexch+1;
 }
 }
 swap(&vec[left], &vec[i]);
 nexch = nexch+1;
 return i;
}
void quickSort(int vec[], int left, int right)
{
 int r;
 if (right > left)
 {
 r = partition(vec, left, right);
 quickSort(vec, left, r - 1);
 quickSort(vec, r + 1,
right);
 }
}
int main()
{ int i;
 int a[N];
 for(i=0; i<N; i++)
 a[i] = rand()%N;
 for(i=0; i<N; i++)
 printf("%d ", a[i]);
 printf("\n\n");
 quickSort(a, 0, N-1);
 for(i=0; i<N; i++)
 printf("%d ", a[i]);
 printf("\n\n");
 scanf("");
 printf("Numero de comparacoes %d\nNumero de trocas %d\n\n",ncomp,nexch);
}
Análise de desempenho
Um dos fatores que influenciam diretamente no tempo de execução do quicksort é o particionamento ser balanceado ou não, podendo leva-lo ao seu pior caso. Abaixo é apresentada a análise empírica do quicksort, com seus dados de tocas e comparações. (ZIVIANI, 2004)
	Análise Empírica do Quicksort
	Esta análise se refere ao Programa 7.
	N
	Melhor
	Médio
	Pior
	
	ncomp
	nexch
	ncomp
	Nexch
	ncomp
	nexch
	1000
	11565
	6033
	11565
	6033
	499500
	999
	2000
	27841
	13607
	27841
	13607
	1999000
	1999
	4000
	61968
	27960
	61968
	27960
	7998000
	3999
	8000
	124977
	67693
	124977
	67693
	31996000
	7999
	16000
	258907
	13027
	258907
	130257
	127992000
	15999
	 Melhor
	O melhor caso é dado quando a partição for balanceada
	Médio
	O médio caso é dado por um vetor aleatório
	Pior
	O pior caso é dado por um vetor já ordenado
	ncomp
	Contador para o número de comparações
	nexch
	Contador para o número de trocas
	
Pior caso 
O comportamento do pior caso para essa ordenação e quando o particionamento escolhe um pivô que faça um subarranjo vir totalmente vazio e o outro com n-1 elementos, para todos os níveis. Dessa forma o tempo para partição será na O(n), somando todos os custos a cada nível de recursão, que nesse caso seria o numero de trocas e comparações feitas, o tempo de execução para o pior caso fica na O(n2). Nesse caso, que ocorre quando o vetor já vem ordenado, uma melhor opção seria a ordenação por inserção. A prova matemática para o tempo de execução do pior caso é a seguinte: Sendo T(n) o tempo no pior caso para uma ordenação de entrada de tamanho n temos (CORMEN et al, 2002): 
T(n) = max(T(q) = T(n-q-1)) + O(n)
Onde q varia de 0 a n-1 pois a partição divide o vetor em dois subvetores. Supondo que 
T(n) <= cn2 , então:
T(n) = max(cq2 + c(n-q-1)2) + O(n) = c.max (q2+ (n-q-1)2) + O(n)
Como q varia de 0 á n-1 então a expressão pode ser trocada pelo quadrado de n-1
T(n) <= cn2 – c(2n-1) + O(n)
T(n) <= cn2
Retirando as constantes multiplicativas e as constantes aditivas, por terem crescimentos insignificantes comparadas ao crescimento da função exponencial, dessa forma tem-se que o tempo de execução será na ordem de n2 (O(n2)).
Figura 3: Exemplo de pior caso do quicksort, particionamento não balanceado. A árvore é dividida em relação ao seu pivô, deixando uma parte vazia e a outra com todos os outros elementos, se tornando algo linear.
Abaixo é apresentado o gráfico para o pior caso comparando o número de comparações e trocas realizadas em relação ao tamanho de elementos que irão ser ordenados.
Melhor caso
Em uma partição que faça com que se produzam dois subvetores de tamanho n/2 e [n/2]-1 ocorre seu melhor caso. Nessa situação a ordenação é feita muito rápida, tendo seu tempo de execução em torno de T(n) <= 2T(n/2) + O(n), e retirando as constantes multiplicativas e as constantes aditivas será de T(n) = O (nlogn). Com seu balanceamento a recursão produz um algoritmo mais assintótico. (CORMEN et al, 2002)
Figura 04: Exemplo de melhor caso do quicksort, particionamento balanceando. A árvore dividida em duas partes iguais, o que agiliza no processo de intercalação.
Médio caso
O tempo do caso médio se aproxima mais do melhor caso do que do pior caso. De acordo com Sedgewick (1998) e Flajolet, o numero de comparações realizadas é:
T(n) = 1,386 nlogn – 0,46n
Retirando as constantes multiplicativas e as constantes aditivas, teremos um tempo de execução de T(n) = O (nlogn). (SEDGEWICK, 1998)
A seguir é apresentado o gráfico para o médio e o melhor caso, pois os dois casos tem tempos de execução bem próximos. No gráfico é comparado o número de comparações realizadas em relação ao tamanho de elementos que irão ser ordenados.
Existem diversos métodos para melhorar o quicksort, um dos mais usados é a mediana de três, que faz uma mediana para achar aquele que seria o melhor pivô e evitar o pior caso. Usando desses artifícios, o quicksort se torna um dos mais rápidos e poderosos algoritmos de ordenação, podendo ser usado em diversas situações. Ele é extremamente eficiente para ordenar dados, necessita apenas de uma pequena pilha e requer cerca de n log n operações em média. Seus aspectos negativos são seu pior caso e o seu método não ser estável.
5.6 Mergesort 
O mergesort é um algoritmo de ordenação por intercalação, sendo essa ordenação a operação de unir dois arquivos ordenados gerando um terceiro arquivo ordenado. Ele obedece ao paradigma dividir e conquistar, sendo que seu funcionamento opera da seguinte forma:
Dividir: divide a sequência de n elementos a serem ordenados em duas subsequências de n/2 elementos cada uma.
Conquistar: recursivamente classificam as duas subsequências, utilizando a ordenação por intercalação.
Combinar: faz a intercalação das duas sequências ordenadas, de modo a produzir a resposta ordenada. (CORMEN et al, 2002)
A operação chave nesse tipo de ordenação é a intercalação de duas sequências ordenadas, no passo de combinar. Para esse processo de intercalação, usamos um procedimento auxiliar chamado MERGE (A, p, q ,r), onde A é um arranjo e p, q e r são índices de enumeração, tais que p <= q < r. O procedimento pressupõe que os subvetores A[p..q] e A[q+1..r] estão ordenados, então ele mescla para formar um único subarranjo ordenado que substitui o subarranjo atual A[p..q]. O procedimento MERGE leva o tempo O(n) e funciona da seguinte maneira: 
Imagina-se duas pilhas de cartas com a face voltada para cima, ambas ordenadas com o menor valor em cima. Deseja-se juntar as duas pilhas (intercalando) em uma única pilha de saída ordenada, que ficará com a face voltada para baixo. O passo básico consiste em escolher a menor das duas cartas superiores e colocá-la virada para baixo na pilha de saída. Esse passo é repetido até que uma das pilhas de entrada esteja vazia, após isso simplesmente coloca-se a outra pilha virada para baixo na pilha de saída. Com isso o processo de intercalação está feito e o vetor está ordenado. (CORMEN et al, 2002) 
Agora se pode usar o procedimento MERGE como uma sub-rotina no algoritmo de ordenação. Os passos do MERGESORT ordenam os elementos do subarranjo A[p..r]. Se p >= r, este subarranjo terá no máximo um elemento, caso contrário o subarranjo será particionado em 2 e chamados recursivamente pela função MERGESORT novamente.
Em seguida é mostrado o código do mergesort em C: 
	Programa 8 - Mergesort
#include <stdio.h>
#include <stdlib.h>
#define N 4000
int ncomp = 0, nexch =0;
void merge(int vec[], int vecSize) 
{
 int mid;
 int i, j, k;
 int* tmp;
 tmp = (int*) malloc(vecSize * sizeof(int));
 if (tmp == NULL) { exit(1);}
 mid = vecSize / 2;
 i = 0; 
 j = mid; 
 k = 0;
while (i < mid && j < vecSize) {
 ncomp = ncomp+1;
 if (vec[i] <= vec[j]) {
 tmp[k] = vec[i++];
 nexch = nexch+1;
 }
 else { tmp[k] = vec[j++];
 nexch = nexch+1;
 } ++k;
 }
 if (i == mid) {
 ncomp = ncomp+1;
 while (j < vecSize) {
 tmp[k++] = vec[j++];
 nexch = nexch+1;
 }
 }
 else {
 ncomp = ncomp+1;
 while (i < mid) {
 tmp[k++] = vec[i++];
 nexch = nexch+1;
 }
 }
 for (i = 0; i < vecSize; ++i) {
 ncomp = ncomp+1;
 vec[i] = tmp[i];
 nexch = nexch+1;
 } free(tmp);
}
void mergeSort(int vec[], int vecSize) {
 int mid;
 if (vecSize > 1) {
 mid = vecSize / 2; mergeSort(vec, mid);
 mergeSort(vec + mid, vecSize - mid);
 merge(vec, vecSize);
 }
}
int main()
{
 int i;
 int a[N];
for(i=0; i<N; i++)
 a[i] = rand()%N;
 for(i=0; i<N; i++)
 printf("%d ", a[i]);
 printf("\n\n");
 mergeSort(a, N);
 for(i=0; i<N; i++)
 printf("%d ", a[i]);
 printf("\n\n");
 scanf("");
 printf("Numero de comparacoes %d\nNumero de trocas %d\n\n",ncomp,nexch);
}
Análise de desempenho
Quando o algoritmo contém uma chamada recursiva, seu tempo de execução geralmente pode ser descrito por uma recorrência, que descreve o tempo de execução global sobre um problema de tamanho n em termos do tempo de execução sobre entradas menores. Então é possível usar ferramentas matemáticas para resolver a recorrência e estabelecer limites sobre o desempenho do algoritmo. (ZIVIANI, 2004)
Para uma melhor análise do tempo de execução do mergesort, imagina-se que o número de elementos será par, para uma divisão em dois subvetores de n/2 elementos. A ordenação por intercalação de apenas um número demora um tempo constante, quando o número de elementos é maior que 1 será da seguinte forma (CORMEN et al, 2002):
Dividir – Essa etapa calcula o ponto médio do subarranjo, o que ira demorar um tempo constante, portanto D(n) = O(1).
Conquistar – Os subproblemas são resolvidos recursivamente e cada um tem tamanho n/2, portanto irão contribuir com 2T(n/2) para o tempo de execução.
Combinar – no combinar o tempo será O(n), pois é o tempo do procedimento MERGE.
Portanto T(n) = O(1) se n=1 e T(n) = 2T(n/2) + O(n) se n>1.
A solução para a recorrência será T(n) = O(nlogn) e para entender intuitivamente a solução utilizaremos a árvore de recursão abaixo. Para facilitar, suponha um tamanho de entrada n sendo uma potência exata de 2. 
Dessa forma T(n) será expandido em uma árvore representando a recorrência. Sua raiz será cn (o custo no nível superior da recursão), e as subárvores são recorrências menores de T(n/2), sendo o custo para cada um dos nós no segundo nível da árvore cn/2. Assim continuamos a desmembrar a árvore ate que o tamanho de seu subproblema seja igual a 1, cada um com custo c. Já com a árvore toda desmembrada somamos os custos através dos níveis, sendo que cada nível custa cn. 
O tamanho da árvore será de log n, e para calcular o custo total simplesmente somamos todos os custos. Dessa forma o custo será cnlogn + cn. Após desconsiderar as constantes multiplicativas e as constantes aditivas, por terem crescimentos de baixa ordem em relação ao n log n, o resultado sera O(nlogn). Abaixo é apresentada a árvore de recursão descrita para entender o tempo de execução.
Figura 5: construção da árvore recursiva, com T(n), e logo apos sendo expandido. Árvore balanceada com seus filhos sendo metade do número de elementos da raiz.
Figura 6: Árvore de recursão totalmente expandida.
Em seguida é apresentada a análise empírica do mergesort, com seus dados de tocas e comparações.
	Análise Empírica do Mergesort
	Esta análise se refere ao ao Programa 8.
	N
	Melhor\Médio\Pior
	
	ncomp
	nexch
	1000
	19662
	19952
	2000
	43356
	43904
	4000
	94753
	95808
	8000
	205481
	207616
	16000
	442877
	447232
	Melhor
Médio
Pior
	O tempo será aproximadamente o mesmo para os três casos.
	ncomp
	Contador para o número de comparações
	nexch
	Contador para o número de trocas
O mergesort apresenta o mesmo tempo de execução para os três casos (Melhor, pior e médio), sempre em torno de O(n log n). A seguir é apresentado o gráfico do número de comparações e trocas realizadas em relação ao tamanho de elementos que irão ser ordenados.
O mergesort se mostra eficiente em ordenações que possam ocorrer pior caso, pois seu tempo de execução será o mesmo para melhor, pior e o médio caso. Suas desvantagens são a utilização de funções recursivas e o gasto extra de memória, pois o algoritmo cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual á (n log n).
5.7 Heapsort
O algoritmo heapsort utiliza o princípio da ordenação por inserção, ou seja, seleciona o maior item do vetor e troca com o item da última posição, depois realiza a mesma operação com os n-1 itens restantes do vetor, então com os n-2 e assim sucessivamente. O heapsort ordena localmente: somente um número constante de elementos do vetor é armazenado fora do vetor que foi dado como entrada em qualquer instante. Outra característica do heapsort é o uso da estrutura de dados heap.
A palavra heap também se refere ao espaço de memória reservado para alocação dinâmica, mas nessa seção falaremos sobre a estrutura de dados. Existem dois tipos de heaps os max-heaps e min-heaps. Um max-heap é um vetor v[1..n] tal que: 
v[i] ≥ v[2i], v[i] ≥ v[2i + 1], para todo i = 1, 2,...,n/2. 
Fica mais fácil de enxergar essa propriedade se o vetor for representado por uma árvore binária completa onde cada nó leva a dois nós menores. Uma árvore binária completa tem os nós numerados de 1 a n, de tal forma que o no 1 é a raiz e o nó [k/2⌋ é o pai do nó k, para 1 ≤ k ≤ [k/2⌋. Dessa forma os nós mais baixos da arvore ficam mais à esquerda no vetor e o item na posição 1 é o maior item do vetor. O min-heap pode ser definido trocando-se o símbolo ≥ na relação por ≤. No min-heap o nó raiz, que é a posição 1 do vetor contém o menor item.
Figura 7: A esquerda, max-heap representado como árvore binária completa. A direita, max-heap representado como vetor.
Função max_heap
A função Max_heap apresentada em linguagem C abaixo recebe como entrada um vetor e uma posição, que é o índice de um nó na árvore. As funções Esquerda e Direita retornam os nós filhos a esquerda e a direita, respectivamente, do nó que foi passado como parâmetro. As comparações determinam se o nó i tem filhos e qual entre eles tem o maior item. Se o índice do maior item for diferente do índice i, então o item guardado em A[maior] é trocado com o item guardado em A[i]. Por fim se a troca for feita a função Max_heap é chamada recursivamente passando o mesmo vetor e o índice maior como parâmetros.
A chamada recursiva ocorre porque ao trocar os elementos A[i] obedece a condição do max-heap, porém A[maior] pode ter violado essa condição.
O tempo de execução de Max_heap em uma subárvore de tamanho n é Θ(1) para achar o maior e trocar com a posição i, mais o tempo para executar Max_heap em um nó filho de i. Como uma subárvore de cada filho tem tamanho máximo igual a 2n/3 o tempo de execução de Max_heap pode ser descrito por: T(n) ≤ T(2n/3) + Θ(1).
Que de acordo com o caso 2 do teorema mestre é: T(n) = O(lg n).
Função 1 - Max_Heap
void Max_heap(Item *A, Indice i) {
 Item aux;
 Indice l, r, maior;
 l = Esquerda(i); //Retorna 2 * i + 1.
 r = Direita(i); //Retorna 2 * i + 2.
 if ((l < n) && (A[l] > A[i])) maior = l;
 else maior = i;
 if ((r < n ) && (A[r] > A[maior])) maior = r;
 if (maior != i) {
 aux = A[i];
 A[i] = A[maior];
 A[maior] = aux;
 Max_heap(A, maior);
 }
}
	
Função Constrói_max_Heap
	A função Constrói_Max_heap recebe um vetor em qualquer ordem e o rearranja na forma de um max-heap. Como cada item depois de A[n/2] é uma folha da árvore e portanto já é um max-heap, podemos começar a construir de n/2 até a primeira posição, onde n é o tamanho do vetor.
	Chamando a função Max_heap no laço for garantimos que cada nó anterior à n/2 + 1 será também um max-heap.
	O tempo de execução da função Constroi_Max_heap pode ser expressado por:
 = 
 Onde h é a altura da árvore e n é o tamanho do vetor.
Resolvendo a direita temos com x = ½ temos:
 = 2.
	
	Assim sendo o tempo de execução de Constroi_Max_heap pode ser dado apenas por:
	 
Então podemos construir um max-heap em tempo linear.
Função 2 – Constrói_Max_heap
void Constroi_Max_heap(Item *A) {
 		Indice i;
 		for(i = n / 2; i > -1; i--)
 Max_heap(A, i);
}
Funcionamento do heapsort
	O heapsort
recebe um vetor a ser ordenado, ele transforma o arranjo em um max-heap chamando a função Constrói_Max_heap e passando como parâmetro o vetor que ele recebeu. O primeiro elemento do vetor agora é o maior, portanto basta troca-lo com o elemento da última posição. Em cada iteração do laço for o tamanho do heap é decrementado, pois posicionar o maior item ele já está ordenado. É importante fazer a manutenção do heap para que o primeiro item seja novamente o maior, isso é feito chamando-se a função Max_heap dentro do laço for.
	Esse algoritmo demora o tempo O(nlogn), pois o procedimento Constroi_Max_heap demora O(n) e cada uma das n-1 chamadas a Max_heap demora O(logn)
	
	Programa 9 - Heapsort
void Heapsort(Item *A) {
 		Indice i;
 		Item aux;
 		Constroi_Max_heap(A);
 	 	for(i = n - 1; i > 0; i--) {
 			aux = A[0];
 		A[0] = A[i];
 		A[i] = aux;
 		n--;
 		Max_heap(A, 0);
 		}
}
Análise
	A ordenação através do Heapsort pode parecer ser pouco eficiente, já que os itens são trocados muitas vezes. Porém a chamada de Max_heap gasta cerca de log n operações, isso no pior caso. Podemos concluir por tanto que, o algoritmo Heapsort leva n log n operações no pior caso. 
	Análise Empírica do Heapsort
	Esta análise se refere ao Programa 9.
	N
	ncomp
	nexch
	1000
	9578
	8078
	2000
	21118
	18118
	4000
	46296
	40296
	8000
	100658
	88658
	16000
	217365
	193365
	ncomp
	Número de comparações
	nexch
	Número de trocas
	Esse tipo de ordenação não é recomendado para vetores pequenos, por conta do tempo necessário para construir o heap, também devemos considerar que o anel interno do Heapsort é muito complexo, principalmente se comparado com o do Quicksort. Entretanto, quando se fala de vetores grandes o Heapsort é melhor que o Shellsort. Algo importante sobre o Heapsort é que ele sempre tem comportamento O(n log n), não importa a entrada. Um ponto negativo é que ele não é estável.
6 ESPAÇO DE COMPLEXIDADE DE UM ALGORITMO
Os métodos de ordenação podem ser classificados de acordo com o espaço de complexidade. Há os que não usam memória extra, exceto talvez por uma pequena pilha; os que usam lista encadeada ou se referem aos dados através de ponteiros ou índices de vetores, e, portanto precisam de memória extra para N ponteiros ou índices; e há os que usam memória extra suficiente para manter uma cópia do vetor a ser ordenado.
Geralmente as restrições de tempo pesam mais que as considerações de espaço. Uma razão para isso é que, na maioria dos programas de classificação, a quantidade de espaço necessário está mais próxima de O(n) do que de O(n²). Uma segunda razão é que, se for necessário mais espaço, quase sempre ele poderá ser encontrado em armazenamento auxiliar. Geralmente, programas que exigem menos tempo demandam mais espaço, e vice-versa.
Os algoritmos elementares apresentados, insertion sort, selection sort, bubble sort e shellsort, possuem complexidade O(1), pois independentemente da quantidade de dados na entrada, o espaço extra utilizado será constante, consumindo apenas a quantidade de memória suficiente para guardar índices que percorrem vetores e variáveis de troca. Os algoritmos sofisticados apresentados, quicksort, mergesort e heapsort, possuem espaço de complexidade O(n), pois é necessário criar uma cópia dos elementos do vetor durante a sua ordenação.
7 CONCLUSÃO
Após analisar diversos algoritmos de ordenação a única afirmação geral que se pode fazer é que não existe a “melhor” técnica geral de classificação. A escolha de uma classificação dependerá necessariamente das circunstâncias específicas.
A maioria dos métodos de classificação clássicos considerados tem exigências de tempo que variam de O(n log n) a O(n²). Entretanto, uma classificação não deve ser selecionada simplesmente por ser O(n log n). A relação entre o tamanho de arquivo n e os outros termos que constituem o verdadeiro tempo de classificação precisa ser levada em conta.
Outra observação a ser feita é que termos que desempenham um papel insignificante para grandes valores de n podem desempenhar uma função importantíssima para pequenos valores de n. Todas essas questões precisam ser analisadas antes de se fazer uma escolha inteligente de classificação.
E várias aplicações de ordenação, um algoritmo simples da ordem de O(n²) pode ser a melhor escolha. Para poucos dados é sempre preferível um método elementar, métodos sofisticados geralmente gastam espaço extra, o que o torna mais lento. Para arquivos de tamanho médio, o shellsort é o mais recomendado, mas para enormes arquivos, onde o tempo de execução é crucial, algoritmos sofisticados será a melhor opção.
REFERÊNCIAS BIBLIOGRÁFICAS
CORMEN, T. H. et al. Algoritmos: Teoria e Prática. Rio de Janeiro: Editora Campus Elsevier, 2002.
QUEIROZ, A. E. de M. Notas de aula da disciplina de Estrutura de Dados II: Quicksort. Bahia: Univasf, 2013.
SEDGEWICK, R. Algorithms in C. 3. ed. Boston: Addison-Wesley, 1998.
STEWART, J. Cálculo. 4. ed. São Paulo: Pioneira Thomson Learning, v. 1, 2001.
TENENBAUM, A. M.; LANGSAM, Y.; AUGENSTEIN, M. Estruturas de dados usando C. São Paulo: Pearson Makron Books, 1995.
ZIVIANI, N. Projetos de Algoritmos: com implementações em Pascal e C. 2. ed. São Paulo: Pioneira Thomson Learning, 2004.