Análise e Complexidade do algoritmo Heap Sort

[pic 1][pic 2]

        

Thiago Henrique Ribeiro Munich – 3628

Análise e complexidade do algoritmo Heap Sort

        

Estudo e pesquisa referente à disciplina SIN 213 - Projeto de Algoritmos, ministrada pelo professor Pedro Moisés de Souza, com objetivo de mostrar os diferentes casos e tempos de execução dos algoritmos listados acima.

Rio Paranaíba – MG                                                                                                                                 2017

RESUMO

           A ordenação ou classificação de dados consiste em receber um montante de dados e organiza-los em ordem crescente e/ou decrescente, a fim de utiliza-los posteriormente. Essa ordenação tem o objetivo de facilitar as buscas e pesquisas por um elemento em um conjunto ordenado. Na computação existe uma série de algoritmos de ordenação, sendo eles de diferentes comportamentos e complexidades, sendo assim, devemos nos atentar ao problema e só depois escolher qual método usar para soluciona-lo.

Sumário

INTRODUÇÃO        4

HEAP SORT        5

Análise de Custo        5

Tabela de Desempenho – Heapsort        6

Gráfico de Desempenho – Heapsort        6

Gráfico de Desempenho Comparativo – Heapsort  X Quicksort Médio        7

Conclusão Heapsort        7

REFERÊNCIAS BIBLIOGRÁFICAS        8

---

INTRODUÇÃO

           Imagine uma lista telefônica cheia de contatos e que você precisa encontrar um deles em específico, agora imagine se estes contatos estiverem totalmente desordenados e não houvesse nenhum método de busca disponível, seria bem trabalhoso encontrar o contato desejado, certo? Para solucionar problemas como estes nós utilizamos os métodos de ordenação.

Na computação existe uma série de algoritmos que utilizam diferentes técnicas de ordenação para organizar um conjunto de dados, eles são conhecidos como Métodos de Ordenação ou Algoritmos de Ordenação.

Os métodos de ordenação se classificam em:

• Ordenação Interna: onde todos os elementos a serem ordenados cabem na memória principal e qualquer registro pode ser imediatamente acessado.
• Ordenação Externa: onde os elementos a serem ordenados não cabem na memória principal e os registros são acessados sequencialmente ou em grandes blocos.

HEAP SORT

           O algoritmo Heapsort faz parte dos algoritmos de ordenação por seleção, é um algoritmo que tem um ótimo desempenho, sendo este melhor quando os conjuntos são ordenados aleatoriamente, tem um consumo razoável de memória, mas o melhor é que seu desempenho no pior caso é praticamente igual ao desempenho no médio caso, ou seja, O(nlogn). O Heapsort utiliza uma estrutura de dados chamada “heap” para ordenar os elementos à medida que os mesmos vão sendo inseridos no vetor. A “heap” pode ser representada melhor como uma arvore binária, para ordem decrescente construímos a “heap-mínima”, onde o menor valor fica na raiz, já na ordem crescente temos o inverso disso, o maior elemento ocupa a posição da raiz, sendo chamado de “heap-máximo”.

Análise de Custo

          Inicialmente o algoritmo não parece eficiente, pois as chaves são movimentadas várias vezes. Entretanto o procedimento max_heapify gasta certa de O(logN) operações no pior caso.
        Portanto, o Heapsort gasta O(nlogn) no pior caso. O Heapsort não é recomendado para arquivos com poucos registros, por causa do tempo necessário para construir o heap, mas continuará sendo O(nlogn) para qualquer tamanho de entrada.                

        

[pic 3]

                                

Tabela de Desempenho – Heapsort

Tabela de desempenho do algoritmo Insertion Sort
Tamanho da entrada	10	100	1000	10000	100000	1000000
Crescente	0	0	0	0	1 segundo	1 segundo
Decrescente	0	0	0,002 segundos	0,159 segundos	1,65 segundos	3,1 segundos
Aleatório	0	0	0,001 segundos	0,079 segundos	2,2 segundos	4,8 segundos

                                    Tabela 1 – Relação tamanho da entrada e tempo gasto para execução.

Na tabela acima podemos acompanhar o desempenho do algoritmo Heapsort de acordo com as entradas do usuário, sendo estas variantes entre 10 e 1.000.000 e o tempo de execução medido em segundos.