Gestalte GoConqr mit. Was sollen wir als Nächstes hinzufügen?

Mindmap

Algoritmos de Ordenação

Aryadne Bastos Portugiesisch

Mapa mental sobre algoritmos de ordenação: ordenação externa, ordenação interna, métodos simples e eficientes

Mapa mental: Algoritmos de ordenação

Inhalt der Mindmap

Algoritmos de Ordenação

  1. 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.
  2. 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  

Informationen

Beschreibung
Mindmap am Algoritmos de Ordenação, erstellt von Aryadne Bastos am 20/09/2020.
Erstellt von
Aryadne Bastos
Aufrufe
5
Bewertung

Mehr zu Algoritmos de ordenação

Feedback

Worum geht es?

Was sollen wir als Nächstes hinzufügen?