Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sorts - Coggle Diagram
Sorts
Força Bruta
Selection Sort
laço i=0-> n-2 vezes (n=tamanho)
Troca os elementos da posição P com o elemento da posição i
Cria um pivô(P) =i
laço de j=i+1 -> n-1
Se o elemento do array na posição j for menor que o elemento na posição P
P vai receber o valor de j
Θ(n²) de comparações para qualquer entrada porem Θ(n-1) troca de elementos
Bubble Sort
Dois for aninhados
De fora de i=0 até n-2 (n=tamanho)
De dentro de j=0 até n-2-i
Se o elemento na posição seguinte(j+1) for maior que na posição atual
Trocar os dois elementos
No pior e no caso médio Θ(n 2 )
Diminuir para conquistar
Procurar a resposta a partir da diminuição de instâncias até que possa ser obtida a resposta
Diminuir por uma constante
O tamanho da instância é reduzido por uma constante em cada interação do algorítimo
Dminuições de tamanho variável
Dividir o tamanho para por uma constate
Diminuir por um fator constante
O tamanho da redução varia em cada interação do algorítimo
Insertion Sort
Laço de i=1 até n-1(n=tamanho)
Salvar o elemento do array da posição i em uma variável v
Salvar o valor de i-1 numa variável j
Laço enquanto j for maior ou igual a 0 e o elemento do array na posição j for maior que v
Elemento do array na posição j+1 vai receber o valor do elemento do array na posição j
j--
Elemento do array na posição j+1 vai receber o valor da variável v
Pior caso pertence a Θ(n²)
Melhor caso pertence Θ(n)
Dividir pra conquistar
Dividir um problema em subproblemas
Encontrar a solução desses subproblemas
Se necessário encontrar entre essas soluçôes a solução do problema
Merge Sort
Criar uma função merge sort
Dividir o array em 2 (A[0 -> n/2-1] e B[n/2-> n-1])
Ordenar o array A e o array B chamando a função mergesort
Fazer o merge dos dois arrays e passar o array A para a função merge(A,B,C)
Função merge
i=0
j=0
k=0
laço enquanto i<(tamanho do array B) e j<(tamanho do array C)
Se B[i]<=C[j]
A[k++]=B[i++]
Caso contrario
A[k++]=C[j++]
Se i== tamanho do array B
Passar todos valores do array C que ainda não estão no array A
Caso não
Passar todos valores do array B que ainda não estão no array A para o array A
Pior caso pertence a Θ(n log n)
Caso mediano também pertence a Θ(n log n)