Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmos de Ordenação - Coggle Diagram

- - - - Operação básica: comparação entre cada elemento da lista e o menor elemento achado até o momento.
        
        O número de vezes que é executada depende apenas do tamanho da lista. C(n) = (n - 1)n/2
        
        O número de trocas é n - 1
        
        É um algoritmo do tipo big-theta(n^2)
  - - - Operação básica: comparação.
        
        C(n) = (n - 1)n/2. C(n) pertence a big-theta(n^2).
        
        O pior caso é se os elementos estiverem em ordem decrescente. Nessa situação, o número de trocas será igual a C(n). No melhor caso, não haverá trocas.
        
        Se em uma percorrida a lista não fizer nenhuma troca, é porque ela já está ordenada.
- - - - A instância do problema é reduzida pela mesma constante, que geralmente é 1, para cada iteração do algoritmo.
        
        Ex: (a^n) = (a^(n-1))*a
        
        Insertion Sort
        
        Algoritmo que utiliza a técnica decrease-by-one para ordenar um array.
        
        Seleciona um elemento "a" do array e compara com os anteriores. O algoritmo vai indicar a posição para inserir "a" no array. Essa posição pode ser zero, se a for menor que todos os elementos antes dele. Se não, "a" será inserido logo após o menor elemento.
        
        Operação básica: comparação de "a" com os elementos do array.
        
        3 more items...
        
        Shell Sort
        
        Algoritmo que faz comparações entre elementos não-adjacentes. Deixa a lista "mais ordenada" para em seguida realizar uma Insertion Sort.
        
        Por exemplo: para uma lista de tamanho 16, primeiramente a quebraríamos em oito sublistas virtuais de tamanho 2. A distância entre cada elemento seria de 8. Então, uma sublista teria um elemento da posição 0 e outro da posição 8 da lista original. Outra teria um elemento na posição 1 e na posição 9.
        
        1 more item...
        
        A eficiência estaria em big-theta(n)
    - - Reduzir a instância de um problema pelo mesmo fator constante, que geralmente é 2, para cada iteração do algoritmo.
        
        Ex: (a^n) = (a^(n/2))^2 se n for par ((a^((n-1)/2))^2)*a se n for ímpar
        1 se n = 0
        
        Nesse caso, a eficiência estaria em big-theta(logn)
        
        Outro exemplo é o algoritmo de busca binária.
    - - O padrão de redução de tamanho varia de uma iteração para outra.
        
        Ex: computar o gcd(m, n) pelo algoritmo de Euclides.
- - - - Se necessário, as soluções para o subproblema são combinadas para obter uma solução para o problema original.
        
        Nem todo divide-and-conquer é necessariamente mais eficiente que uma solução por força bruta.
        
        Técnica mais utilizada em computações paralelas onde cada subproblema pode ser resolvido simultaneamente pelo seu próprio processador.
        
        Uma instância de n pode ser dividida em "b" instâncias de tamanho n/b com "a" delas precisando ser resolvidas.
        
        T(n) = a*T(n/b) + f(n)
        
        f(n) é uma função que conta o tempo gasto dividindo uma instância de tamanho n em instâncias de tamanho n/b e combinando suas soluções.
        
        1 more item...
  - - - Ordena um array dividindo-o em duas metades e ordenando cada uma delas recursivamente. Depois, une os dois arrays menores ordenados em um único.
        
        C(n) = 2*C(n/2) + Cmerge(n)
        
        No pior caso, Cmerge(n) = n - 1
        
        Logo, pelo teorema mestre, Cworst(n) pertence a big-theta(n*logn)
        
        Vantagem: estabilidade.
        
        Desvantagem: quantidade linear de espaço extra que o algoritmo precisa.