Licenciatura em computação

UNIVERSIDADE ESTADUAL DA PARAÍBA CCT - CENTRO DE CIÊNCIA E TECNOLOGIA

TERCIO BARBOSA SILVA

ANÁLISE EXPERIMENTAL DOS ALGORITMOS ELEMENTARES DE ORDENAÇÃO: INSERTION SORT, BUBBLESORT E SELECTIONSORT.

CAMPINA GRANDE – PB 10/09/2012

TERCIO BARBOSA SILVA

ANÁLISE EXPERIMENTAL DOS ALGORITMOS ELEMENTARES DE ORDENAÇÃO: INSERTION SORT, BUBBLE SORT E SELECTION SORT.

Trabalho apresentado ao professor Fabio Leite da disciplina Estrutura de Dados, turno tarde do curso de Licenciatura em Computação.

CAMPINA GRANDE – PB 10/09/2012

INTRUDUÇÃO

Na ordenação de dados tomamos como ponto de partida os algoritmos elementares de ordenação Insertion Sort, Bubble Sort e Selection Sort. Daremos foco a sua implementação em pseudo-código, uma forma de linguagem mais simples, como também em Java, linguagem utilizada atualmente na disciplina de Estrutura de Dados para qual estamos desenvolvendo a análise dos algoritmos. Veremos como tais algoritmos funcionam como também a corretude, eficiência e custo. Mais adiante veremos seus tempos de execução para a ordenação dos dados com diversos tamanhos de entrada, analisando em casos isolados, como também comparando com os demais tipos de ordenação em questão.

Algoritmos de Ordenação
Em diversas situações de análise de dados se torna inevitável à organização para maximizar a eficiência de determinadas tarefas. Uma delas é ordenar os elementos em uma determinada sequência, facilitando desta maneira a análise, compreensão e manipulação dos dados para posteriores tratamentos. Uma das formas mais simples para a ordenação de dados são os algoritmos de ordenação elementares, dentre eles destacam-se o Insertion Sort, Bubble Sort e o Selection Sort.

Insertion Sort
Algoritmo de ordenação elementar por inserção. Compara elemento por elemento e os ordena da esquerda para direita, possui bom desempenho para ordenação de uma pequena quantidade de elementos. Para uma grande quantidade de elementos torna-se inviável devido a sua característica de acentuar