Algoritmos de ordenação

NOME: MILLER

Algoritmos de Ordenação
250 200 150 100 50 0 Insertion Sort 100 200 1000 3000 10000 15000 35000 50000 80000 100000 150000 200000 300000 400000

INSERTION SORT O insertion sort é um bom algoritmo para ordenar pequenas quantidades de elementos. Basicamente, ele varre um array da esquerda para a direita(ou vice-versa) e vai deixando os elementos mais à esquerda (ou direita) ordenados. No trabalho, foi sugerido fazer 3 variações desse algoritmo. Os gráficos dos tempos de execução de cada variação estarão logo abaixo. Cada bloco colorido indica um vetor que foi organizado pelo algoritmo. O tamanho de cada vetor está na legenda mais à direita, e os tempos em segundos ,à esquerda. É interessante notar que o Insertion Sort original, para o maior vetor (100000 elementos) chega a possuir um tempo de ordenação maior que 12s, enquanto o algoritmo com busca binária não passa de 1s. O método binário elimina comparações desnecessárias, e isso justifica tal feito. Para vetores suficientemente grandes, a troca de um Insertion Sort por um Insertion Sort com Busca Binária vale muito a pena, mesmo a implementação podendo ser mais difícil.

16 14 12 10 8 6 4 2 0 Insertion Sort com Busca Binária

100 200 1000 3000 10000 15000 35000 50000 80000 100000 150000 200000 300000 400000

2,5

2

1,5

1

0,5

0 Insertion Sort Memcpy

100 200 1000 3000 10000 15000 35000 50000 80000 100000 150000 200000 300000 400000

2,5

2

1,5

1

0,5

0 Insertion Sort Memmov

100 200 1000 3000 10000 15000 35000 50000 80000 100000 150000 200000 300000 400000

MEMCPY E MEMMOV Se podemos considerar o Insertion Sort com Busca Binária um bom algoritmo, o que dizer quando implementamos Memcpy e Memmov? A eficiência nesses comandos está em fazer a movimentação de blocos, ao invés da monotonicidade da movimentação elemento a elemento. A velocidade é relativamente alta e a diminuição de custo é relativamente grande, como podemos ver depois nos gráficos gerados. A