Aps Ordenação

UNIP – Universidade Paulista

Ciência da Computação (CC)

&

Sistemas de Informação (SI)

Atividades Práticas Supervisionadas (APS)

1º semestre de 2011.

Tema:

“Desenvolvimento de Sistema para Análise de Performance de Algoritmos de Ordenação de Dados”

Sumário

1. Objetivo do Trabalho 3

2. Introdução 4

3. Referencial Teórico 7

4. Desenvolvimento 10

5. Resultados e Discussões

6. Considerações Finais

7. Referências Bibliográficas

8. Código Fonte

9 Relatório com as Linhas de Código

Objetivo do Trabalho

As Atividades Práticas Supervisionadas dos 2º e 3º Semestres de 2011 do Curso de Ciência da Computação têm como objetivo a pesquisa bibliográfica a respeito dos principais algoritmos de ordenação de dados e o desenvolvimento de sistema computacional completo, utilizando a linguagem de programação Java, que obtenha os dados, efetue a ordenação e compare os desempenhos entre três técnicas selecionadas, além da elaboração de uma monografia sobre os aspectos teóricos que envolvem o projeto, bom como sobre todos os assuntos relativos ao desenvolvimento do sistema computacional.

Introdução

A análise de desempenho dos algoritmos de 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 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-a mais eficiente.

A seguir, serão apresentados os mais conhecidosalgoritmos 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 idéia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. No melhor dos casos o algoritmo executa n2 operações relevantes, onde n representa o número de elementos do vetor e no pior dos casos, são feitas n2 operações. A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.

Algoritmo do Pente (Comb Sort):

É um algoritmo de ordenação relativamente simples. A idéia básica é eliminar os pequenos valores próximos do final da lista, já que em um bubble sort estes retardam a classificaçãotremendamente. O Algoritmo, repetidamente, reordena os diferentes pares de itens, separados por um salto, que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente.

Quicksort:

É um método de ordenação muito rápido e eficiente. O Quicksort é um algoritmo de ordenação por comparação não-estável, seguindo a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada.

Ordenação por Mistura (Merge Sort):

Sua idéia básica é criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.