Algoritmos de ordenacao
Analise de desempenho
Andrew Ramies May
Universidade Federal de Rondonia
UNIR
Porto Velho - RO
andrewc3po@gmail.com
Resumo: Analise e desempenhos de algoritimos de ordenacao:
Todos os tres algoritimos tem como complexidade (n2)
bubble, insertion e selection sort. Com codigo fonte em C/C++.
para o pior caso de teste. [1]
Palavras-chave; Algoritmos; ordenacao; bubble; insertion;
A. Bubble sort
selection;
Metodo de ordenacao que percorre o vetor da esquerda para
a direita varias vezes colocando o maior valor no final da
I.
INTRODUCAO
estrutra.
A necessidade de ordenar informacoes e inerente em uma
aplicacao, por isso muitos programas tem como sub-rotina
B. Selection Sort
algoritmos de ordenacao, isso faz com que seu estudo seja
Metodo de ordenacao contrario ao bubble sort, procurando
muito importante, porem em computacao o tempo de uma
colocar sempre o menor valor da sequencia na primeira
rotina e muito importante, pois nao e nada interessante para o
posicao.
usuario ficar um minuto esperando o computador terminar de
executar uma tarefa porque o algoritmo foi mal projetado.
Existe uma grande diversidade de algoritmos de ordenacao, e
C. Insertion Sort
cada um depende de muitos fatores para um bom desempenho,
Metodo de ordenacao que sempre faz comparacoes com o
que seram mostrados ao longo deste artigo.
elemento anterior verificando se e menor, caso verdadeiro e
feita uma troca de posicoes, e novamente e feita a verificacao
II.
V
com o elemento anterior a troca, ate encontrar um valor maior
ISAO GERAL
ou o fim do vetor, depois volta a comparar o elemento posterior
A. Execucao do programa
do primeiro loop.
O programa pode ter N casos de testes, para cada caso de
D. Analise dos testes
teste, e necessario entrar com um numero inteiro N >= 0, este
inteiro ira geral uma lista duplamente encadadeada de tamanho
N inicialmente em ordem decrescente. Em seguida uma
250
funccao e chamada contendo o algoritmo bubble sort, deixando
a lista crescente, e uma linha e impresa como o tempo de
200
execucao desta funcao, em seguida e executado outro bloco
com o algoritimo insertion sort colocando a lista em ordem
decrescente e novamente imprimindo uma linha com o tempo
150
de execucao, e em seguida e feito o chamando da funcao que
contem o selection sort programando para ordenar a lista em
100
ordem crescente e imprimindo novamente o novo tempo de
execucao. Assim o loop e finalizado e o programa ira aguardar
a entrada de outro numero inteiro para executar o loop
50
novamente (0 finaliza o programa).
o
p 0
B. Link do codigo fonte
m
e
4000
8000
20000
60000
20000
T 2000
6000
10000
40000
80000
http://paste.lymas.com.br/2439
Entrada
Bubble Sort
Insert Sort
Select sort
III.
IMPLEMENTACAO DOS ALGORITMOS
Para fins didaticos todos os algoritmos exemplificados
serao tratados como o objetivo de transformar a estura em uma
estrura em ordem crecente.

---

IV.
CONCLUSAO
encadeada, exigindo pouco conhecimento em programacao
Para todos os algoritmos foi obtido um tempo de execucao
para a compreensao do codigo fonte.
bem parecido, quando o N estava proximo a 0, porem quanto
Os 3 algoritmos analisados nao sao recomendados para um
maior era o N maior a diferenca no tempo de execucao. Todas
projeto real pois se em determinado momento for necessario
as estruturas submetidas para ordenacao eram com o pior caso
ordenar uma grande estrutura, o programa pode demorar alguns
possivel, essas estruturas sao geradas altomaticamente, e o
segundos para responder, ou ate minutos.
tempo para gerar a estrutura nao e utilizado no calculo dos
blocos de ordenacao, sendo assim o tempo de execucao
impresso e confiavel.
REFERENCIA
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
A implementacao foi feita na linguagem de programacao
Stein, "Algoritmos - Teoria e pratica" pp.99-152 Junho 2012.
C++ a estrutura de dados utilizada e uma lista duplamente

---

Document Outline

• ﾿
• • 
  • ﾿
• • 
  • ﾿
  • 
• ﾿

---