Ajude a dar forma ao GoConqr. O que a gente deve adicionar?

Mapa mental

Algoritmos de ordenação

Giovanna Cardoso Colodetti Português

Mapa mental sobre algoritmos de ordenação: método estável, método não estável, QuickSort e Bubblesort

Mapa mental: Algoritmos de ordenação

Conteúdo do mapa

Algoritmos de ordenação

  1. Método estável

    • Shakersort
      • Semelhante ao Bubblesort, porém com melhor desempenho
      • Faz a ordenação do vetor tanto na esquerda quanto na direita, movendo os maiores valores para o fim e os menores para o começo
      • Começa a verificar do final para o começo e depois do começo para o final, repete o processo até o vetor estar ordenado
      • Seu melhor caso é quando o vetor está ordenado, já o pior é quando está inversamente ordenado
      • Melhor caso: O número de comparações é C(n) = O(n) e movimentação M(n) = 0
      • Pior caso: O número de comparações é C(n) = (n^2) e movimentação M(n) = (n^2)
      • Método lento e redundante, pois refaz comparações já feitas antes
    • Inserção Direta
      • Eficiente para vetores quase ordenados ou quando se deseja adicionar poucos itens
      • Pior caso: Tanto o número de comparações quanto o de movimentações é QUADRÁTICO (C(n) = (n2) e M(n) = (n2))
      • Melhor caso: O número de comparações e o de movimentações é LINEAR (C(n) = (n) e M(n) = (n)).
      • Vetor é dividido em 2 subvetores
      • Inicialmente o primeiro segmento contém um único elemento e conseqüentemente está ordenado. O segundo segmento contém os (n-1) elementos restantes
    • Bubblesort
      • Método simples e de fácil entendimento
      • Chaves são comparadas em pares, onde são trocadas caso fora de ordem
      • Procedimento é repetido para valores não ordenados
      • Melhor caso: É alcançado quando o conjunto de dados já está ordenado. (Para o melhor caso o número de comparações é Linear C(n) = O(n) com zero movimentações M(n) = 0)
      • Método lento exceto em casos onde o conjunto possui apenas algumas chaves desordenadas. Em casos onde apenas a última chave está desordenada o número de comparações é igual ao do pior caso
      • Não aproveita muito dos passos anteriores, realizando comparações redundantes
  2. Método não estável

    • Seleção direta
      • Verificar o menor valor e o coloca na primeira posição do vetor, e repetir o processo com os valores ainda não ordenados
      • Possui C(n) = O(n^2) de comparações mas sua movimentação é linear M(n) = O(n)
      • Ideal para arquivos grandes
      • Um dos algoritmos mais simples de ordenação
    • QuickSort
      • É um dos métodos mais eficientes
      • Pior caso: Acontece quando o pivô escolhido é um dos extremos de um conjunto de dados já ordenado.
      • Melhor caso: Acontece quando, em todas as etapas, o vetor for dividido ao meio.
      • Este método não é ideal para arquivos já ordenados quando a escolha do pivô não é boa
    • Shellsort
      • Método simples e de fácil implementação, porém, não foi possível mensurar a razão de sua eficiência
      • Conjunto de dados é comparado em pares, onde a distância entre os pares é calculada de forma específica onde cada incremento não pode ser múltiplo do anterior
      • Melhor caso: É alcançado quando os elementos já estão ordenados. -> Para o melhor caso o número de comparações é C(n) = O(n^1,25).
      • Pior caso: É alcançado quando os elementos estão inversamente ordenados. -> Para o pior caso o número de comparações é C(n) = O(n*(ln(n))^2).
      • Ideal para uso em casos de mais de 5.000 chaves, o tempo de execução varia de acordo com o número de arquivos fora de ordem.

Informações

Descrição
Mapa Mental sobre Algoritmos de ordenação, criado por Giovanna Cardoso Colodetti em 05-09-2022.
Visualizações
7
Avaliação

Mais sobre Algoritmos de ordenação

Fale Conosco

Sobre o que é sua mensagem?

O que a gente deve adicionar?