APS - ATIVIDADES PRÁTICAS SUPERVISIONADAS DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

INSTITUTO DE CIÊNCIAS EXATAS E TECNOLOGIA-ICET CIÊNCIA DA COMPUTAÇÃO

ATIVIDADES PRÁTICAS SUPERVISIONADAS

ARARAQUARA – SP

2014

COLABORADORES

APS – ATIVIDADES PRÁTICAS SUPERVISIONADAS DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

Atividades Práticas Supervisionadas desenvolvimento de um sistema apresentado como exigência para avaliação,

em disciplina do 3º semestre, do curso de Ciência da Computação da Universidade Paulista, sob orientação do professor Leandro Fernandes

1º semestre de 2014.

ARARAQUARA – SP

2014

SUMÁRIO

1 OBJETIVO............................................................................................................... 4

2 INTRODUÇÃO ........................................................................................................ 5

3 REFERENCIAL TEÓRICO ...................................................................................... 8

4 DESENVOLVIMENTO........................................................................................... 12

5 RESULTADOS ...................................................................................................... 23

6 CONSIDERAÇÕES FINAIS................................................................................... 29

7 BIBLIOGRAFIA...................................................................................................... 30

8 CÓDIGO FONTE ................................................................................................... 32

1 OBJETIVO

Atividades Práticas Supervisionadas, do 3º Semestre do Curso de Ciências da Computação de 2014, será realizar uma pesquisa bibliográfica a respeito dos principais algoritmos de ordenação de dados e o desenvolvimento de um sistema computacional completo, utilizando a linguagem de programação Java. Selecionando três ou mais técnicas, e que obtenha os dados, efetue a ordenação e compare os desempenhos entre eles.

A unidade de medida para efeito de comparação deverá ser o tempo total de ordenação. Os dados que serão utilizados para as ordenações deverão ser externos (obtidos a partir de valores previamente armazenados, tais como arquivos texto) e internos (valores aleatórios gerados pelo próprio programa ou fornecidos diretamente pelo usuário).

2 INTRODUÇÃO

A ordenação de dados, é objeto de estudos bastante aprofundados por diversos órgãos, instituições acadêmicas e pesquisadores do mundo inteiro. O resultado desses estudos é comum até a afirmação de que, para cada tipo de aplicação, existe um tipo de algoritmo de ordenação mais apropriado, depois disso, há uma diversidade de conceitos obtidos, cada um muito bem justificado por seus estudiosos e apresentados como mais eficientes, conforme seus conceitos.

Existem vários algoritmos de ordenação de dados, que foram inventados, ou implementados, conforme foram surgindo necessidades de aprimoramentos dos métodos utilizados ao longo das últimas décadas, tendo em vista o aumento da quantidade de dados que passaram a serem registrados de alguma forma.

Com o advento tecnológico da informação, milhares de informações são processadas instantaneamente, permitindo o uso simultâneo de dados armazenados em diversos sistemas, sendo necessárias consultas, inserções, exclusões ou alterações em pouquíssimo espaço de tempo, a ponto de não se perceber, humanamente, o tempo gasto na execução dessas determinadas tarefas.

Para alcançar a eficiência necessária, na manipulação de dados de uma variedade considerada de tipos de informações, existem alguns fatores determinantes, que fazem toda a diferença entre cada uma das técnicas utilizadas para ordenação dos dados, sejam elas simples ou complexas.

Ordenação de dados consiste, basicamente, em organizar os elementos de determinada sequência de forma ordenada com o objetivo de facilitar a busca da informação desejada, tornando-as mais eficiente.

A seguir, serão apresentados os mais conhecidos algoritmos de ordenação existentes e, dentro de uma análise breve, o histórico, vantagens e desvantagens de cada um deles:

Ordenação por Inserção (Insertion Sort):

É um algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados.

Ordenação por Seleção (Selection Sort):

É um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os elementos restantes, até os últimos dois elementos.

Ordenação por Flutuação (Bubble Sort):

É um algoritmo de ordenação com a ideia é percorrer

...