WelBrabo

Passo 1 - Apresentar explicações sobre as análises realizadas neste estudo: por que houve reclamações de clientes com relação a desempenho e se existe um algoritmo de ordenação que pode ser usado como padrão para qualquer.

Os algoritmos tem características únicas nos quais apresentam desempenho superior conforme a entrada no sistema (quantidade de dados) e recursos disponíveis:

 Selection

Características Desvantagens

Interessante para arquivos pequenos O fato de o arquivo já estar ordenado não ajuda

em nada, pois o custo continua quadrático.

O algoritmo não é estável.

 Bubble

Características Desvantagens

Para o usuário, não há vantagem. Percorre a estrutura muitas vezes, por isto se torna ineficiente.

 Insertion

Características Desvantagens

Eficiente quando a estrutura está "quase ordenada".

Boa escolha caso deseja inserir elementos aos poucos. Estável. O pior caso quando os itens estão originalmente na ordem reversa.

 Merge

Características Desvantagens

Recomendado para aplicações com restrição de tempo. A complexidade do merge sort é a mesma para o pior, médio e melhor caso. Independente da situação dos dados no vetor, o algoritmo irá sempre dividir e intercalar os dados. Utiliza memória auxiliar, já que utiliza outros vetores para as subordenações. Alto consumo de memória

 Shell

Características Desvantagens

A razão da eficiência do algoritmo ainda não é conhecida. Ninguém ainda foi capaz de analisar o algoritmo. A sua análise contém alguns problemas matemáticos muito difíceis. O que se sabe é que cada incremento não deve ser múltiplo do anterior.

Shellsort é uma ótima opção para arquivos de

tamanho moderado. O tempo de execução do algoritmo é sensível à

ordem inicial do arquivo.

O método não é estável,

 Quick

Características Desvantagens

O pior caso ocorre quando, sistematicamente, o pivô é escolhido como sendo um dos extremos de um arquivo já ordenado.

Isto faz com que o procedimento Ordena seja

chamado recursivamente n vezes, eliminando apenas um item em cada chamada.

Extremamente eficiente para ordenar arquivos de dados.

Necessita de apenas uma pequena pilha como

memória auxiliar. Em seu pior caso, realiza o mesmo número de comparações que o Bubble sort.

Não é estável.

Possui várias versões, o que pode trazer diversos problemas e diferenças de desempenho, como as versões utilizadas nos testes.

 Binary Tree Search

Características Desvantagens

Ordenação rápida. Foi um dos melhores métodos de ordenação testados.

Melhor rendimento com menor quantidade de elementos.

As árvores binárias são uma das estruturas

de dados mais importantes devido a grande

aplicabilidade das mesmas. Torna o processo de busca mais lento, devido a possibilidade de alta profundidade da árvore.

Seu desempenho depende da quantidade e ordem dos elementos de entrada.

 

 AVL Tree

Características Desvantagens

Objetiva buscas mais rápidas. Ordenação lenta devido aos inúmeros processos de calculo dos fatores de balanceamento e balanceamentos.

Sua ordenação foi uma das mais demoradas.

 B-Tree

Características Desvantagens

Arvore-B é uma estrutura balanceada projetada para trabalhar com dispositivos de armazenamento secundário como dispositivos magnéticos. Utilizada para manipular muitos dados, sendo utilizada por SGBDs e manipulação de arquivos.

Economia de memória. Mais adequada a arquivos voláteis do que árvores binárias. Performance de busca por chave é idêntica a da árvore binária, se só ponteiros para nodos são empilhados.

Nodo não-folha com m chaves é visitado m vezes.

Desta forma, a padronização de um algoritmo de busca consistirá em perda de desempenho nas operações básicas (inserção, busca e remoção). Para se evitar desagrados dos clientes, deve-se escalar para uma determinada tarefa, um algoritmo com características favoráveis resultando em melhores desempenhos.

Passo 2 - Apresentar os principais aspectos que devem ser levados em consideração no momento da escolha do método a ser usado para ordenar uma base de dados e mantê-la ordenada. Para isso deverão considerar principalmente: a dimensão da base de dados; o número de execuções de ordenação realizadas pelo sistema e o número de buscas realizadas pelo sistema.

Resultados dos testes de dados aleatórios:

As tabelas acima demonstram o desempenho médio dos algoritmos, uma referência mais próxima de um caso real.

Como podemos constatar nos mais variados testes (como na Etapa 2), a entrada no sistema é um