Mind map
Algoritmos de Ordenação

Mapa mental: Algoritmos de ordenação
Map content
Algoritmos de Ordenação
Ordenação Externa
- Ocorre quando o arquivo não cabe na memória principal e deve ser armazenado em fita ou disco. Neste tipo de ordenação, os registros são acessados sequencialmente ou em grandes blocos.
Ordenação Interna
- Ocorre quando o arquivo a ser ordenado cabe todo na memória principal. Neste tipo de ordenação, qualquer registro pode ser imediatamente acessado.
- Métodos Simples
- O (n2) comparações - arquivos pequenos. Produzem programas pequenos e fáceis de entender.
- ShakerSort - Coqueteleira
- *Tem como objetivo melhorar o desempenho do bubblesort; * Faz muitas trocas assim como o bubblesort, o que faz dele tbm um dos menos eficientes. * É um método estável.
- BubbleSort - Bolha
- * Faz muitas trocas, o que o torna o menos eficiente! * É um método estável; * Se o arquivo estiver quase ordenado ele costuma ser eficiente, mas deve-se tomar cuidado com o caso em que o arquivo está ordenado. Se o menor elemento estiver na última posição, o algoritmo fará o mesmo número de comparações do pior caso;* É um método MUITO lento, pois só compara posições adjacentes - uma do lado da outra;* Cada passo aproveita muito pouco do passo anterior; * Comparações redundantes, pois o algoritmo é linear e obedece a uma sequência fixa de comparações. Então ele pode fazer a mesma coisa várias vezes.
- Seleção Direta
- * Um dos algoritmos mais simples; * Número de movimentações é linear; * Bom para arquivos com registros grandes; * Bom para arquivos com até 1000 registros se a chave tem tamanho igual a 1 palavra; * Se o arquivo já está ordenado ou quase, isso não ajuda em nada!! C(n) continua quadrático; * Algoritmo não é estável.
- Inserção Direta
- * Bom pra quando está quase tudo organizado; *om pra ADICIONAR poucos itens, de forma ORDENADA, pois ele é linear; *Estável.
- Métodos Eficientes
- O (n logn) comparações - arquivos grandes. As comparações usadas são mais complexas nos detalhes.
- QuickSort
- * Precisa, em media de n logn, para ordenar N itens; * não é estável;* Precisa de uma pilha como memória auxiliar;* Implementação delicada e difícil. Qualquer engano pequeno pode levar a erros inesperados.* A versão recursiva tem como pior caso O(n2) operações;
- MergeSort
- * Requer o dobro de memória, ou seja, precisa de um vetor com as mesmas dimensões do vetor que está sendo usado; * é capaz de ordenar um vetor qualquer de n de elementos em um tempo proporcional a nlgn; * não importa a maneira como os elementos estão organizados no vetor, sua complexidade será sempre a mesma.
- HeapSort
- * Não é estável; * Não é recomendado para arquivos com poucos registros devido ao tempo necessário para se construir a heap !
- ShellSort
- * Permite troca de registros de posições distantes; * Não se sabe POR QUE ele é eficiente; * Código Pequeno; * Opção boa para mais ou menos 5000 registros; * Não estável
Information
- Description
- Mind Map on Algoritmos de Ordenação, created by Aryadne Bastos on 20/09/2020.
- Created by
- Aryadne Bastos
- Views
- 5
- Rating
More on Algoritmos de ordenação