Mapa mental
Algoritmos de ordenação

Mapa mental: Algoritmos de ordenação
Conteúdo do mapa
Algoritmos de ordenação
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
- Shakersort
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.
- Seleção direta
Informações
- Descrição
- Mapa Mental sobre Algoritmos de ordenação, criado por Giovanna Cardoso Colodetti em 05-09-2022.
- Criado por
- Giovanna Cardoso Colodetti
- Visualizações
- 7
- Avaliação
Mais sobre Algoritmos de ordenação