DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

[pic 1]     [pic 2]

UNIP – Universidade Paulista

1. Ciência da Computação (CC)

DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

Bruno Xavier da Silva                              A75804-6

Isaías Dias Paranhos                              B16096-9

Ruan da Silva Pereira                       A65HFG-6

Tabatha Lourenço                             A832JH-2

Jundiaí - SP

2012

Sumário

OBJETIVO3

INTRODUÇÃO4

1. BUBBLE SORT5
2. SELECTION SORT6
3. INSERTION SORT7
4. QUICK SORT8
5. DESENVOLVIMENTO9

5.1. Obtenção de Dados9

5.2. Processos para Ordenação10

5.3. Listagem de Valores11

5.4. Apresentação dos Resultados11

1. RESULTADOS E DISCURSÃO12
2. CONSIDERAÇÕES FINAIS14

BIBLIOGRAFIA15

CÓDIGO FONTE16

OBJETIVO

Temos por objetivo neste trabalho apresentar os principais algoritmos de ordenação (ou classificação) mostrando os detalhes da técnica e toda a sua complexidade e desenvolver um sistema computacional completo que obtenha os dados e efetue a ordenação. Assumindo a mesma entrada para os diferentes algoritmos. Com isso, espera-se comparar o tempo de execução e apresentar as complexidades dos algoritmos. A unidade de medida para efeito de comparação será o tempo total de ordenação.

INTRODUÇÃO

Ordenação de dados é a técnica de classificar, deixar organizada uma determinada estrutura de elementos. As principais formas de ordenação são em ordem numérica e alfabéticas, tanto pode ser decrescente como também crescente.

Uma das principais razões para se ordenar uma estrutura é a eficiência que será proporcionada ao acesso de dados após a ordenação. Analisando uma lista telefônica podemos entender a necessidade de estar organizado, assim, imagine se a lista telefônica fosse feita de forma aleatória e não por ordem alfabética. Com certeza demoraríamos muito mais tempo para identificar a posição de uma pessoa na lista. O que traz um atraso significativo na pesquisa e gera um certo de estresse da pessoa que a realiza.

Para realizar a organização dos dados existem diversos algoritmos como o Insertion sort, Selection sort, Bubble sort, Shell sort, Heap sort, Merge sort, Quick sort, entre outros. Selecionamos três algoritmos distintos para implementar e analisar o seu desempenho. São eles: Bubble sort, algoritmo por flutuação que consiste em percorrer o vetor diversas vezes jogando sempre o maior elemento para o final; Quick sort, algoritmo muito rápido e eficiente, que trabalha usando a metodologia divisão e contista; e Selection Sort algoritmo de organização por seleção; e Insertion Sort, algoritmo que trabalha por inserção.

1. BUBBLE SORT

O Bubble Sort é um dos algoritmos de ordenação mais simples que existe. Segundo a tradução ele é um método de bolhas, também chamado de método por flutuação. Consiste em percorre o vetor diversas vezes, levando sempre o maior valor para a última posição e fixando está posição para que não seja alterada.

Ilustração do método:

[pic 3]

Como podemos ver na figura acima, o vetor é varrido diversas vezes encontrando o maior valor (na cor vermelha), e o colocando na última posição. A cada passagem a última posição é fixada (na cor azul), diminuindo o tamanho do vetor a se varrido da próxima vez.

Complexidade para qualquer caso é .[pic 4]

1. SELECTION SORT

O método de seleção (Selection Sort) busca o menor valor do vetor a ser ordenado e o coloca na primeira posição, fixando essa posição para que não faça mais parte da próxima busca. Este processo se repete até que o vetor seja completamente ordenado.

Ilustração do método:

[pic 5]

        Analisando a figura acima, podemos ver que há uma troca entre o primeiro elemento de cada busca como o menor elemento da parte desordenada do vetor.

Complexidade:

• Pior caso: ;[pic 6]
• Melhor caso: [pic 7]

1. INSERTION SORT

Este método de ordenação por inserção é eficiente em pequenos vetores. Consiste em varrer o vetor da esquerda para a direita, e conforme avança ele vai mantendo o lado esquerdo do vetor organizado.

Ilustração do método:

[pic 8]

A figura acima mostra o processo feito por este método para ordenar os elementos. Conforme o sistema anda de casa em casa do vetor, ele vai organizando o elemento selecionado na parte esquerda do vetor, ou seja, a cada elemento que ele seleciona ele procura sua posição na parte esquerda do vetor, mantendo esta sempre organizada.

Complexidade para qualquer caso .[pic 9]

1. QUICK SORT

Um algoritmo rápido como o próprio nome diz, o Quick Sort funciona de forma recursiva. Consiste em pegar uma chave, organizar o vetor colocando de um lado os maiores que a chave e do outro os menores. Por ser recursiva, tanto a parte menor quanto a parte maior, viram vetores distintos que vão ter outra chave e organizar da mesma maneira, assim sucessivamente até chegarmos a um vetor de apenas um elemento.

...