Algoritmos de Ordenação

Rafael Alves C. Feitosa, Cleiton S. Moura, Pedro Alex L. Martins Departamento de Informtica e Estatstica Universidade Federal do Piau (UFPI) Teresina, PI - Brasil rafael-feitosa,cleitonmoura18,[e-mail]Abstract. This paper deals with the study and comparison of the major sorting algorithms, InsertionSort, SelectionSort, BubbleSort, MergeSort, HeapSort QuickSort and, based on the analysis of execution time and complexity of each algorithm. Resumo. Este artigo trata do estudo e comparao dos principais algoritmos de ordenao, InsertionSort, SelectionSort, BubbleSort, MergeSort, HeapSort e QuickSort, com base na analise do tempo de execuo e complexidade de cada algoritmo. 1. Introduo O trabalho apresentado tem como objetivo analisar os algoritmos InsertionSort, SelectionSort, BubbleSort, MergeSort, HeapSort e QuickSort, implementados para a ordenao de um arranjo em ordem crescente, decrescente e aleatria, com entradas de 1000, 5000, 10000, 20000 e 30000 elementos. Para cada ordem e entrada ser examinado o tempo de execuo do algoritmo para verificar e comparar a complexidade do algoritmo com os demais. A mquina para efetuar os testes dos algoritmos foi um computador do laboratrio do Departamento de Informtica e Estatstica (DIE) da Universidade Federal do Piau (UFPI) com processador Intel Core 2 Quad de 2.66GHz, memria (RAM) de 2GB, utilizando o sistema operacional Windows Vista de 32bits. A linguagem de programao utilizada para implementar os algoritmos foi a Java, desenvolvida no NetBeans IDE 6.8. Existe uma numerosa quantidade de algoritmos para resolver o problema da ordenao, cada algoritmo utiliza um mtodo para ordenar, que dependendo da aplicao, possui vantagens em relao aos outros. A maioria dos algoritmos escolhe um elemento do arranjo (chave) para comparar e realizar trocas com os demais a fim de controlar a ordenao. A ordenao de um arranjo pode ser interna ou externa. Na ordenao interna os elementos so ordenados no arranjo original, enquanto na