Please enable JavaScript.

Coggle requires JavaScript to display documents.

Força Bruta, Selection Sort, Dividir para conquistar (Divide and Conquer)…

- - - - f(n)->tempo para dividir o problema geral em subproblemas
- - - - Próximo do mínimo teórico que qualquer algoritmo de ordenação baseado em comparações pode ter
  - - - Estabilidade
    - - Quantidade de armazenamento exigida
  - - - Divide a lista e ordena cada parte recursivamente e mescla
        
        Classificar arquivos que residem na memória secundária
        
        Mesclagem de múltiplas vias
    - - Mescla pares de elementos e depois mesclam-se os pares classificados
      - Evita sobrecarga de tempo e espaço usando uma pilha para chamadas recursivas
- - - - Começa com a solução para uma instância menor do problema
        
        Abordagem Incremental
- - - - Exemplo: Algoritmo de Euclides
        
        Embora o valor do lado direito seja sempre menor do que o do lado esquerdo, não diminui por uma constante ou por um fator constante
- - - - Array A[0...n-2] já foi ordenado
    - - Ordenar um Array A[0...n-1]
        
        Achar uma posição para inserir um elemento de forma ordenada
        
        Geralmente faz-se o scanning do subarray da direira para a esquerda até achar o primeiro elemento menor ou igual a A[n-1] e inserir logo após aquele elemento.
  - - - Número de comparações depende do tamanho da entrada
        
        Melhor Caso
        
        Comparação (A[j]>v) é executada somente uma vez para cada iteração
        
        Θ(n) time
        
        Melhor caso de matrizes classificadas não é muito útil pois não podemos esperar sempre entradas convenientes
        
        Porém arquivos quase ordenados surgem em uma variedade de aplicações e o Insertion Sort tem excelente desempenho
        
        Caso Médio
        
        Θ(n^2) time
        
        Desempenho de caso médio 2x mais rápido e excelente eficiência em matrizes quase ordenadas
        
        Faz o Insertion Sort se destacar entre os algoritmos de ordenação Selection e Bubble Sort
        
        Investiga o número de pares que estão fora de ordem
        
        Mostra que em matrizes ordenadas aleatoriamente a Insertion Sort faz metade das comparações do que em matrizes decrescentes
        
        Pior caso
        
        Matriz estritamente decrescente
        
        Θ(n^2) time
        
        Comparação (A[j]>v) é executada o maior número de vezes
        
        Faz o mesmo número de comparações da Selection Sort